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