반응형
[문제 출처]
https://www.acmicpc.net/problem/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])
반응형
'알고리즘 > python' 카테고리의 다른 글
[python/파이썬] 백준 14430 자원 캐기 (0) | 2022.07.18 |
---|---|
[python/파이썬] 백준 11060 점프 점프 (0) | 2022.07.18 |
[python/파이썬] 백준 17212 달나라 토끼를 위한 구매대금 지불 도우미 (0) | 2022.07.15 |
[python/파이썬] 백준 17175 피보나치는 지겨웡~ (0) | 2022.07.14 |
[python/파이썬] 백준 9461 파도반 수열 (0) | 2022.07.14 |