[파이썬 / 백준 1699번] 제곱수의 합

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

728x90

N=int(input())
square=[i*i for i in range(1,317)]
dp=[0]*(N+1)
for i in range(1,N+1):
    s=[]
    for j in square:
        if j>i:
            break
        s.append(dp[i-j])
    dp[i]=min(s)+1
print(dp[N])