[BOJ]1699_제곱수의 합

📃 제곱수의 합

코드

import sys
input = sys.stdin.readline 
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값을 1부터 n까지 하나씩 갱신해가는 방법이다. 즉 작은 방법부터 해결해 나가는 전형적인 DP문제이다.

i로 1부터 n까지 돌면서, j는 1부터 i-1까지의 수 중 제곱한 값이 i보다 크지 않아야 한다.