백준 - DP (#1699)

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

주어진 자연수 N을 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

Code

n = int(input())
dp = [0]
squares = [x*x for x in range(1,int(n**0.5)+1)]

for i in range(1,n+1):
    temp = []
    for j in squares:
        if j > i:
            break
        temp.append(dp[i-j])
    dp.append(min(temp) + 1)

print(dp[n])