파이썬) 백준 알고리즘 | 1699번 : 제곱수의 합

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

1699번: 제곱수의 합

 

pseudo code

dp 배열을 만든다
dp[i]에는 dp[i-1]과 dp[i-n^2]들을 비교해서 최솟값을 할당한다
dp[-1]을 출력한다

 

import math
n = int(input())
dp = [0] * (n+1)

for i in range(1, n+1):
    a = math.floor(i**0.5)
    dp[i] = min(dp[i-1]+1, dp[i-a**2]+1)
    for j in range(a):
        dp[i] = min(dp[i], dp[i-j**2]+1)
print(dp[-1])