[C#] 백준 1789번 수들의 합

[ 문제 ]

서로 다른 N개의 자연수의 합이 S라고 한다. S를 알 때, 자연수 N의 최댓값은 얼마일까?

 

[ 코드 ]

1. 내 코드

- 이진탐색 알고리즘 사용

StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

long n = long.Parse(sr.ReadLine());

long left = 1;
long right = n;
long result = 0;

while (left <= right)
{
    var mid = (left + right) / 2;
    var sum = (mid * (mid + 1)) / 2;

    if(sum <= n)
    {
        result = mid;
        left = mid + 1;
    }
    else
    {
        right = mid - 1;
    }
}

sw.Write(result);
sw.Flush();
sw.Close();
sr.Close();

 

2. 다른 사람 코드 참고

- 1부터 증가하여 n의 합을 초과하지 않는 제일 큰 수를 출력한다. 

StreamReader sr = new StreamReader(new BufferedStream(Console.OpenStandardInput()));
StreamWriter sw = new StreamWriter(new BufferedStream(Console.OpenStandardOutput()));

long n = long.Parse(sr.ReadLine());

long num = 1;
long result = 0;

while (true)
{
    result += num;
    if (result > n) break;
    num++;
}

sw.Write(--num);
sw.Flush();
sw.Close();
sr.Close();

 

입력이 200이 주어졌을 때 200이 넘지않는 합은 1~ 19까지의 합인 190이다. 자연수는 19개가 있는데 이 값이 최대로 구할 수 있는 개수인 것이다.

딱 200이 되는 합중에 아래의 예를 보면 이 수들의 개수는 19개 이다.

{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 13, 14, 15, 16, 17, 18, 20, 21}

 

[ 실행화면 ]

case: 1

 

 

 

 

---

문제링크: https://www.acmicpc.net/problem/1789

1789번: 수들의 합