[Python]1699. 제곱수의 합

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

1699번: 제곱수의 합

---

dp[i-1] 이 아닌 dp[i-j^2] 을 이용해서 제곱수의 합을 DP로 구현하는 것이 포인트.

dp[i] = min(dp[i-j^2])+1, 1<=i<=n, 1<=j^2<=i 

+1 을 하는 이유는, 경우의 항의 갯수 이므로 항이 하나 늘어난다는 의미이다.

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