[백준/파이썬] 1699번 제곱수의 합

-Code

import sys
input = sys.stdin.readline

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

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

처음에 while로 해서 큰 수부터 빼주는 방법으로 시도하여 특정 값에서 다른 출력이 나와 실패를 하고 여러 입력값에 대한 개수를 직접 써보고 했으나 dp로 구현을 못해서 어디 값을 가져와야 하는지에 대해서 찾아보고 해결을 했으나 아쉬웠습니다.