백준 온라인 저널, 그리디 알고리즘/1789번 : 수들의 합(파이썬)

문제 정의

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

 

 

입력

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

 

 

출력

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

 

 

예제 입력 1

200

예제 출력 1

19

 

- 최대한 많은 자연수를 사용해 S를 만들기 위해선 서로 다른 자연수들이 최소가 되어야한다.

 

1+2+3+4 = 10이다.

1+2+3+5 = 11이다.

1+2+4+5 = 12이다.

1+3+4+5 = 13이다.

2+3+4+5 = 14이다.

1+2+3+4+5 = 15이다.

=> 따라서 i가 1부터 N까지일 때 ∑K = X인 경우에, K는 X <= S <= X+1의 조건을 만족할 때 구할 수 있다는 것을 알 수 있다.

 

(위의 식이 성립하는 이유는 ∑K = X에 대한 N이 0부터 N까지의 차이가 모두 1이기 때문에 자연수에 한해서 위의 식은 성립한다.)

 

 

 

접근 방법

1. 주어진 S보다 작아질 때까지 숫자를 하나씩 더하다가 S보다 작으면 (N-1)을 출력한다.

 

 

코드

s = int(input())
total = 0
count = 0

while True:
    count += 1
    total += count
    if total > s:
        break

print(count-1)