[Python] 백준 1699 제곱수의 합

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

1699번: 제곱수의 합

 

 

문제해결

dp를 이용해야겠다라는 생각이 든다!

 - y를 제곱수의 합으로 표현할 때 최소개수를 dp[y]라고 하고 x를 y보다 작은 제곱수라고 가정하면 dp[y] = min(dp[y], dp[y-x] + 1)

만약 어떤 수 y가 제곱수이면 dp[y] = 1 인 것이 명백하므로 먼저 제곱수는 dp[y] = 1을 고정시키자.

for 문을 쓰면 될 것 같은데?

 

 

code

import sys
input = sys.stdin.readline

n = int(input())
dp = [x for x in range(n+1)]　＃ｘ는　ｄｐ［ｘ］의　ｍａｘｉｍｕｍ　값이다．　
＃왜냐하면　ｄｐ［ｘ］　＝　１＋１＋．．．１　제곱수　１을　ｘ번　더한　것으로　나타낼　수　있기　때문이다．
for i in range(n+1):
    for j in range(1,i+1):
        if j*j > i:
            break
        if dp[i] > dp[i-j*j] + 1:　
            dp[i] = dp[i-j*j] +1　＃　참고로　문제　해결　전에는　미리　ｉ＝ｊ＊２　이면　ｄｐ［ｉ］＝１로
            ＃고정　시킬려고　했다．　하지만　이렇게　코드를　작성하면　ｄｐ［ｉ］　＝　ｄｐ［０］＋１　이　되므로　ｄｐ［ｉ］　＝　１　이　된다．
print(dp[n])