출처 | https://www.acmicpc.net/problem/1789

코드

a = int(input())
cnt = 0
rs = 0


while True:
    cnt += 1
    rs += cnt

    if rs > a:
        break

print(cnt-1)

코드설명

1. 수들을 어떻게 선택할 것인가?

   문제에서 주어진 자연수 S를 만들기 위해 어떤 자연수들을 선택해야 하는지 고민해보아야 한다. 주어진 수 S를 만드는 데 필요한 최소한의 수를 선택하는 것이 목표다.

2. 가장 작은 자연수부터 선택한다.

   가장 작은 자연수 1부터 시작하여, 차례대로 선택해보면서 주어진 수 S를 초과하지 않을 때까지 선택한다. 즉, 1부터 시작하여 1, 2, 3, 4, ... 순으로 선택해보면서 S를 초과하지 않는 최대의 수를 찾는다.

3. 합을 계산하면서 진행한다.

   수를 선택하면서 그 수들의 합을 계속 업데이트한다. 만약 합이 주어진 수 S를 초과하면, 그 이전 단계에서 선택한 수 중 하나를 제외하고 다음으로 큰 수를 선택하는 방식으로 계속 진행한다.

4. 최소한의 수를 선택하면서 합을 만들어 나간다.

   목표는 주어진 수 S를 만들기 위해 필요한 최소한의 수를 선택하는 것이므로, 합을 만들어 나갈 때 가능한 최소한의 수를 선택해야 한다.