[백준] 1699 제곱수의 합 (파이썬 python)

 

 

문제 링크

 

 

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

1699번: 제곱수의 합

 

 

문제

 

 

 

 

 

문제 풀이

 

 

i가 현재 숫자, j가 i보다 작은 제곱수들일 때,

dp[i - j] 중 가장 최소항의 개수가 작은 것을 찾아낸다.

이 값에 1을 더해주면 i의 최소항의 개수가 나타난다.

(1을 더해주는 이유는 제곱수에 대한 항의 수를 추가하기 위해서이다.)

점화식 => dp[i] = min(dp[i - j]) + 1

 

 

n = int(input())
dp = [0 for i in range(n + 1)]
square = [i * i for i in range(1, 317)]
for i in range(1, n + 1):
    s = []
    for j in square:
        if j > i:
            break
        s.append(dp[i - j])
    dp[i] = min(s) + 1
print(dp[n])