[Python] 제곱수의 합 - 백준 (DP)

해당 글은 백준 1699번 문제 '제곱수의 합'을 다룬다.

문제

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

1699번: 제곱수의 합

 

설명

해당 문제는 DP로 해결할 수 있고, 점화식을 아래와 같이 표현된다.

현재 숫자 i에서 1~(i-1)까지 값을 j라고 했을 때, 해당 값의 제곱한 결과를 뺀 dp값 + 1이 작다면 dp값을 업데이트 해준다. 

if dp[i] > dp[i-j**2]+1:
    dp[i] = dp[i-j**2]+1   

 

코드

n = int(input())

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