[백준1699] 제곱수의 합

문제

---

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

1699번: 제곱수의 합

 

생각의 흐름

---

dp[i]에는 i라는 수를 만들기 위해 필요한 제곱수들의 최소 항의 갯수를 계산해 저장한다. 그 후 j를 1부터 sqrt(i)까지 증가시키며 dp[i-j*j]+1을 계산해 최소항의 수를 계산한다.

 

코드

---

# 백준 1699
import sys

n = int(input())
dp = [i for i in range(n+1)]

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