백준 python 1699 제곱수의 합

백준 링크:https://www.acmicpc.net/problem/1699

1699번: 제곱수의 합

그리드 문제인줄 알고 도전했다가 실패했던 문제다.

dp를 사용하면 오류없이 도출가능

 

각 제곱수인 1,4,9 ''' 316 까지의 수를 저장해놓은 matrix를 사용해서 그 수가 나온만큼 뒤로 백하면 된다.

import math
n=int(input())
# 16까지 [0,1,2,3,1,2,3,4,2,1,2,3,3.2,3,4,1] 변하는수 =[4,8,9,12,13,16]

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

개인적으로 어떻게 해야할지 몰라서 한시간이나걸렸다