[백준/Python3] 1699 제곱수의 합

https://www.acmicpc.net/problem/1699

---

풀이

자연수 N을 그보다 같거나 작은 제곱수의 합으로 나타날 때, 최소의 항의 갯수를 구하는 문제다. Dynamic Programming을 이용해 해결할 수 있다.

dp[i] = i를 나타내는 제곱수 의 합 중 가장 최소 갯수

일단 기본적으로 자연수 N은 1^2 + ... + 1^2` = N 으로 최대 N개의 항으로 나타낼 수 있다. 그러므로 기본 DP table은

dp[i] = i

로 초기화한다.

i의 제곱수의 합 중 가장 최소의 개수로 나타내는 식은 다음과 같다.

for j in range(1, i):
	if i - j**2 < 0:
    	break
    # j의 제곱수를 dp[i - j**2]에 더하기 때문에 항의 개수는 1이 더해진다.
    if dp[i] > dp[i - j**2] + 1:
    	dp[i] = dp[i - j**2] + 1

이를 1부터 N까지의 반복문들 돌리면 dp[n]의 값을 구할 수 있다.

코드

import sys
input = sys.stdin.readline

# Initial
N = int(input())
MAX = 100000
answer = 0

# Make dp table
dp = [0 for _ in range(MAX + 1)]
dp[1] = 1 # 1 = 1^2

for i in range(2, MAX + 1):
    dp[i] = i
    for j in range(1, i):
        if (j**2) > i:
            break
        if dp[i] > dp[i-j**2] + 1:
            dp[i] = dp[i-j**2] + 1
            
# Answer
answer = dp[N]
print(answer)