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

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

n = int(input())

dp = [100001]*(n+1)
dp[0] = 0
for i in range(1, n+1):
    for j in range(1, int(i**0.5)+1):
        if dp[i] > dp[i-j**2] + 1:
            dp[i] = dp[i-j**2] + 1

print(dp[n])