백준 1699번 파이썬 문제풀이(DP - 제곱수의 합)

---

이 문제는 우선 개수를 쭉 구해보고 규칙이 있는지 찾아봐야 한다.

0 - 0개

1 - 1^2 (1개)
2 - 1^2 + 1^2 (2개)
3 - 1^2 + 1^2 + 1^2 (3개)
4 - 2^2 (1개)
5 - 2^2 + 1^2 (2개)
6 - 2^2 + 1^2 + 1^2 (3개)
7 - 2^2 + 1^2 + 1^2 + 1^2 (4개)
8 - 2^2 + 2^2 (2개)
9 - 3^2 (1개)
10 - 3^2 + 1^2 (2개)
11 - 3^2 + 1^2 + 1^2 (3개)
12 - 2^2 + 2^2 + 2^2 (3개)
13 - 3^2 + 2^2 (2개)
14 - 3^2 + 2^2 + 1^2 (3개)
15 - 3^2 + 2^2 + 1^2 + 1^2 (4개)
16 - 4^2 (1개)

 

와 같이 나온다. 

여기서 규칙을 찾아야 하는데 코드로 치면 한 두줄밖에 안되는데도 사실 이부분을 빠르게 생각하기가 쉽지는 않다.

우선 정답부터 말하자면 dp[i] = min(dp[i - (j * j) ]) + 1 이 된다.

예를 들어서 보는 것이 이해하기에 쉽다. 

i가 16이라면 j * j는 1~16이 될 수 있다. 여기서 j * j 는 최대 1 4 9 16 4개만 존재한다. 그렇다면 dp[i - 1], dp[i - 4], dp[i - 9], dp[i - 16]중 가장 작은 값은 dp[0] = 0이고 여기에 1을 더한 값을 dp[i]에 넣어준다. 왜 이런식이 나오는지에 대해 생각을 해보면 17을 가정할때 16(17-1)일때 횟수에서 +1 을 할 수 있고 (17-4)인 13일때 횟수에서 +1 일수도 있고 (17-9)인 8일때 횟수에서 +1을 할수도있고 (17-16)일때인 1일때의 횟수에서 +1 을 해도 되기 때문에 다음과 같은 식이 나온다.

 

import math
import sys

N = int(sys.stdin.readline())

# 각각의 수를 1^2 으로 표현할때가 가장 큰 횟수이기 때문에 인덱스와 동일하게 x로 초기화
dp = [x for x in range(N+1)]


for i in range(1, N + 1):
    for j in range(1, int(math.sqrt(i) + 1)):
        if dp[i] > (dp[i - j * j] + 1):
            dp[i] = dp[i - j * j] + 1
        
print(dp[N])