[백준 1789] 수들의 합 (실버 5) Python

 

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

1789번: 수들의 합

---

문제

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

입력

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

출력

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

---

풀이 방법

 서로 다른 n개의 자연수를 더해서 s를 만들어야 한다. 이때 더하는 자연수의 종류를 가장 많이 갖는 경우를 구해야 한다. n의 최댓값을 구하려면 작은 수부터 차례로 더해서 s를 만드는 방법을 찾아야 한다. 1부터 s까지 for문을 돌면서, s-1, s-2... 를 반복하다가 s가 0이하가 되면 for문을 종료한다. 이때 마지막 반복 때 s에서 차감했던 수가 곧 n이 된다.

반복문 종료 후 만약 s가 음수가 되었을 경우 i에서 1을 빼준 후 리턴하고, s가 0이라면 i를 그대로 리턴해준다.

 

# 백준 1789 수들의 합
# 서로 다른 n개의 자연수의 합이 s일 때, 자연수 n의 최댓값은?
s = int(input())

if s == 1:
    print(1)
    exit()

for i in range(1, s):
    s -= i
    if s <= 0:
        break

result = i
if s < 0:
    result -= 1

print(result)