백준 1789. 수들의 합

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

1789번: 수들의 합

 

서로 다른 n개의 자연수의 합이 s일때, n이 최대가 되도록 하려면

작은 수들끼리 더해야 n이 최대가 될것이다.

 

sum이 1부터 순서대로 더했을때 1+2+3+... 값이라고 한다면

s-sum이 마지막으로 더한값보다 작다면 s를 만들기 위해 필요한 수가 이미 쓰인 자연수이기 때문에 불가능하다.

 

예를들어 s=200이면 

1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18 = 171 이다.

200-171=29 이므로 뒤에 29를 더하면 19개로 200을 만들수 있다.

 

그런데 

1+2+3+4+5+6+7+8+9+10+11+12+13+14+15+16+17+18+19 = 190 이다.

200-190은 10이므로 200을 만들려면 10이 필요한데 10은 이미 쓴 자연수 이므로 불가능하다.

 

 

#include <iostream>
using namespace std;

int main()
{
    long long n;
    cin >> n;
    long long sum = 0;
    int cnt;
    for(int i = 1; i <= n; i++)
    {
        sum += i;
        if(n-sum <= i)
        {
            cnt = i;
            break;
        }
    }
    cout << cnt;
}