[Algorithm] BAEKJOON 1789번: 수들의 합 (C++)

https://www.acmicpc.net/problem/1789

 

 

 

 

문제

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

 

입력

첫째 줄에 자연수 S(1 ≤ S ≤ 4,294,967,295)가 주어진다.

 

출력

첫째 줄에 자연수 N의 최댓값을 출력한다.

 

 

 

 

 

풀이

그리디 알고리즘을 사용하여 해결하였다. 최대한 많은 수의 자연수를 포함시키는 것이 목표이므로 가장 작은 수부터 순서대로 더하는 것이 가장 효과적인 전략이다.

 

 

C++ 소스 코드

#include <iostream>
using namespace std;

int main() {
    unsigned long long S;
    cin >> S;

    unsigned long long sum = 0;
    int N = 0;
    for (int i = 1; sum + i <= S; i++) {
        sum += i;
        N = i;
    }

    cout << N << endl;
    return 0;
}