[python/파이썬] 백준 1660 캡틴 이다솜

[문제 출처]

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

1660번: 캡틴 이다솜

 

[문제 풀이]

 

PyPy3로 제출해야 시간 초과가 나오지 않는다.

import sys
input = sys.stdin.readline

n = int(input())

balls = []
num = 0
a = 1

while n > num:
    num += (a*(a+1))//2
    balls.append(num)
    a += 1

dp = [300001 for _ in range(n+1)]
for i in range(1,n+1):
    for b in balls:
        if b==i:
            dp[i] = 1
            break
        if b > i:
            break
        dp[i] = min(dp[i], dp[i-b]+1)
    
print(dp[n])