[Python/DP] 제곱수의 합 (헷갈림)

문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=32+12+12(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=22+22+12+12+12(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

예제 입력	예제 출력
7	4
1	1

---

풀이

문제 읽고 그리디 문제인줄 알았음 

그런데 이렇게 풀면 61 = 36+25로 답은 2인데, 49+9+1+1+1이라는 오답이 나옴

=> DP로 풀어야 함

# ***오답
N = int(input())
square_num = []

i = 1
while i**2 <= N:
    square_num.append(i**2)
    i += 1

answer = 0
for i in range(len(square_num)-1, -1, -1):
    if N >= square_num[i]:
        answer += N//(square_num[i])
        N = N%(square_num[i])

print(answer)

dp[i]는 i의 제곱수의 합의 최소 개수

점화식: dp[i] = min(dp[i - j]) + 1  ****1은 제곱수 j를 한 번 더한다는 횟수의 시각에서 생각
i가 숫자, j가 i보다 작거나 같은 제곱수들

예를 들어 i가 16이라고 했을때 i보다 작거나 같은 제곱수는 1, 4, 9, 16이다. 
dp[i - 1], dp[i - 4], dp[i - 9], dp[i - 16]중 가장 작은 값은 0이고 여기에 1을 더한 값을 dp[i]에 넣어준다.

 

# *** 정답
import sys
input = sys.stdin.readline

N = int(input())
dp = [x for x in range(N+1)] # dp[x]의 최대(최악값은) 1을 x개만큼 했을 때

for i in range(1, N+1): # dp[N]까지 값을 찾는다
    for j in range(1, i): # dp[1]일때 1*1, dp[2]일때 1*1, 2*2(break),... dp[10]일때 1*1, .., 3*3, 4*4(break)
        if j*j > i:
            break
        if dp[i] > dp[i-j*j] +1: # 더 작은 dp[i-j*j]의 값을 발견하면
            dp[i] = dp[i-j*j] + 1
print(dp[N])