알고리즘 - Python / 백준 - 1789번 : 수들의 합

1789번: 수들의 합 (acmicpc.net)

1789번: 수들의 합

 

---

풀이

• 서로 다른 N개의 자연수의 합이 S라 하고 S를 알 때 N의 최댓값을 구하는 문제이다.
• N을 가장 크게 만들기 위해서는 1부터 계속 더해가면서 그 값을 만들면 된다.
• 1,2,3... 을 S에서 뺴주면서 S < 빼는 수 일 때 break 하고 그때의 값을 출력한다.
• ex) S = 5 -> 1 ( S=4 ) , 2 ( S=2) , 3 ( S=2 < 3 이므로 남은 S값인 2를 모두 전 값에 더해버림)
• 결과적으로 S = 5 인 경우는 1 , 4 로 이루어질 수 있다.

 

import sys
a = int(sys.stdin.readline())
cnt = 1
ans = 0
while True:
    if a < cnt:
       break
    else:
        a = a - cnt
        cnt += 1
        ans += 1
print(ans)

---