[백준]1699 제곱수의 합 #dp

1.풀이

N보다 작은 수들을 가지고 dp[N]를 만들 수 있는 방법은 다음과 같다

​

(N-1^2) + 1^2

(N-2^2) + 2^2

(N-3^2) + 3^2

.

.

.

​

따라서 dp[N]을 자연수 N의 최소 제곱수의 개수라고 할때 점화식을

dp[N]=min(dp[N-1^2],dp[N-2^2],dp[N-3^2]...)+1로 나타낼 수 있다.

​

2.소스코드

import math
INF=9876543210
N=int(input())
dp=[i for i in range(N+1)]
dp[0]=0
for i in range(1,N+1):
    j=1
    while(1):
        power=j**2
        if i<power:
            break
        else:
            dp[i]=min(dp[i],dp[i-power]+1)
            j+=1
print(dp[N])