백준 1699 파이썬 (제곱 수의 합)

문제 : https://www.acmicpc.net/problem/1699

💻 Code

n = int(input())
dp = [k for k in range(0, n+1)]
print(dp)
for i in range(1,n+1):
    for j in range(1,i):
        if(j*j > i):   
            break
        dp[i] = min(dp[i], dp[i-j*j]+1)

print(dp[n])

점화식이 엄청 어려웠던 문제..