1789. 수들의 합

(실버 V) 그리디 문제 - 서로 다른 N개의 자연수의 합이 S일 때, N의 최댓값을 구하기.

문제 링크: https://boj.kr/1789

1. 풀이

서로 다른 N개의 자연수의 합이 S일 때, N의 최댓값을 구하는 문제이다.

가장 작은 수들로 합을 이루었을 때 N이 가장 클 것이므로, 가장 작은 수부터 차례로 조합을 찾아나가면 된다.

단, 19의 경우: $19=1+2+3+4+5+…$ 를 하게되면 마지막에 $4$가 남는다. 서로 다른 수만 사용할 수 있으므로 이러한 경우, 마지막에 더해진 $5$와 남은 수인 $4$를 더한 $9$가 마지막 덧셈 수가 되면된다.

2. 코드

s = int(input())

count = 0
while s > 0:
    count += 1
    s -= count
if s < 0:
    count -= 1

print(count)