🟩 [백준] [Python] [Silver2] 1699번_제곱수의 합

문제

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

1699번: 제곱수의 합

풀이

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