1789. 수들의 합

문제

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

입력

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

출력

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

Example 1

입력 200
출력 19

풀이

그리디 알고리즘

예제를 입력을 확인해보자. 최대한 많은 숫자를 사용해서 200을 만들려면 가장 작은 수부터 차례대로 더하면 된다.
-> 200 = 1 + 2 + 3 + 4 + 5 + ... + n
이렇게 더하다 보면 200을 넘어가는 경우가 생긴다.
-> 1 + 2 + ... + 18 + 19 + 20 = 210
19까지 더하고 10을 다시 더하면 딱 200이 되지만, 문제에서 서로 다른 N개의 자연수를 사용하라고 명시하였기 때문에 10을 다시 사용할 수는 없다.

따라서 최대한 많은 자연수를 사용하는 경우는 1부터 순차적으로 더해나가다 S를 초과할 때, (마지막으로 더해준 값) + (S가 되는데 필요한 값)을 더한 값을 사용하면 된다.
ex. 1 + 2 + ... 18 + 19 + 20 일 때, 200을 초과하게 되므로 20을 빼고, 19(마지막으로 더해준 값) + 10(S가 되는데 필요한 값)인 29를 더해주면 200이 된다.

하지만 출력해야 하는 값은 사용한 자연수의 개수이므로 18 + 1 = 19가 되는 것이다.

소스

s = int(input())

sum = 0
answer = 0
while sum <= s :
	answer += 1 # 1부터 순차적으로
    sum += answer # 더해준다.

print(answer - 1)