[백준] 1699번 제곱수의 합

💡문제접근

• 처음엔 당연히 그리디 알고리즘이라고 생각해서 코드를 작성했는데 WA를 받았다. 질문게시판을 참고해보니 어느 분이 답변하길... "항상 큰 제곱수를 빼준다고 해서 최적의 해가 나온다고 100% 장담할 수 없다."는 것이었다.
• 결국 직접 제곱수 최소 항의 개수를 구해서 점화식을 세웠다.

💡코드(메모리 : 115112KB, 시간 : 188ms, PyPy3로 제출)

import sys
input = sys.stdin.readline

N = int(input().strip())

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

💡소요시간 : 14m