제곱 수의 합 실버 2 (백준, DP)

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

 

dp테이블에 n까지의 수를 미리 입력한다.(n까지의 모든 수의 최대항의 합. 예로 5는 (1^2)*5이다.)

그 후 이중for문으로 탐색을 하는데, 탐색하는 수의 제곱이 현재값보다 높으면 더이상 원하는 값을 찾을 수 없으므로 반복문을 탈출한다.

(모든 수를 탐색, 판단하는 경우를 방지한다.)

 

그 외의 경우는 현재의 제곱수 항들과 현재수에서 탐색하고 있는 j의 제곱수를 빼준 값에 1을 더한 값 중 작은 값을 dp테이블에 넣어준다.

이때 j의 제곱수를 빼준 값에 1을 더해주는 이유는
i가 5인 경우일 때 생각해보면, 5는 2^2+1^2로 현재값 5에서 4(1개의 항,현재값 i보다 작은 가장 큰 제곱 수)를 빼준 것에 대한 보상이기 때문이다.

 

결국 dp[i-j*2]라는 문장은 현재값에서 가장 큰 값을 빼줬을 때 남는 값의 항 수를 dp테이블에서 참조한 것이 되는 것이고,
현재값의 항 수 5(1^2) 보다 2^2의 항 수 + dp[1](1의 제곱 수)가 더 작은 수가 되기 때문에 최소항의 합을 구할 수 있다.