글 읽기 - dp로 시간초과

gwanwoo3849 1년 전 0

dp구현을 했는데 생각보다 육각수가 많아서 1부터 1000000까지 각각 육각수를 돌아보는걸로는 시간초과가 나네요... 힌트 부탁드립니다 ㅜㅜ

n=int(input())
l=[1]
a,i=1,2
while a<n:
    a=i*(2*i-1)
    l.append(a)
    i+=1
dp=[0]
k=len(l)
for i in range(1,n+1):
    j=0
    s=6
    while j<k and l[j]<=i:
        s=min(s,dp[i-l[j]]+1)
        j+=1
    dp.append(s)
print(dp[-1])

댓글을 작성하려면 로그인해야 합니다.

문제

문제

출처

ICPC

dp로 시간초과

gwanwoo3849 1년 전 0

Baekjoon Online Judge

채점 현황

문제

유저 대회

고등학교 대회

출처

대학교 대회

도움말