[백준][C++] 1789: 수들의 합

문제

1789번: 수들의 합

풀이

그리디

 

가장 작은 자연수인 1부터 N을 넘기 직전까지 더해간다. N이 200이면 다음과 같다.

1 + 2 + 3 + ... + 18 + 19 = 190

다음 수인 20을 더하면 210이므로 200을 초과한다. 여기서 더해지는 자연수는 중복되면 안 되므로, 마지막 수인 19를 29로 바꾸면 합이 200이 된다. 

즉, 1부터 더한 값이 넘을 때까지의 자연수의 개수 - 1이 정답이다. 

코드

#include <iostream>

using namespace std;


int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cout.tie(NULL);

    long long N;
    cin >> N;

    // 최대한 작은 자연수부터 더하면서 마지막에 N을 만들 수 있도록 알 맞는 수를 더한다.
    // 1 + 2 + 3 + ... + (N을 만드는 수)
    long long sum = 0;
    long long current = 1;
    int answer = 0;
    while (sum <= N)
    {
        sum += current;
        current++;

        answer++;
    }

    cout << answer - 1;

    return 0;
}