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

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

1699번: 제곱수의 합

 

---

풀이 과정

문제를 보면 떠오르는건 주어진 자연수 N을 가장 큰 제곱수로 계속 빼나가는 그리디 방법이다.

 

7, 1, 4, 11, 13의 문제에서 주어진 모든 입력에서 그리디로 풀면 적절한 답이 나오므로 이게 정답일것 같지만 반례가 존재한다.

61 = 36 + 25로 N이 61일때 제곱항의 최소 수는 2인데 그리디로 풀면 49 + 9 + 1 + 1 + 1로 제곱항의 수가 5가 나온다.

 

d[i] => 자연수 i를 제곱수들의 합으로 표현할 때 제곱항의 최소 개수라고 하자. 그러면

d[i] = min(d[i-j*2]) + 1 (1 <= j*2 <= i) 라는 점화식이 성립한다.

 

 

 

 

---

소스 코드

import sys

N = int(sys.stdin.readline())
d = [i for i in range(100001)]
d[0] = 0

for i in range(2, N+1):
    j = 1
    while j*j <= i:
        if d[i] > d[i-j*j] + 1:
            d[i] = d[i-j*j] + 1
        j += 1

print(d[N])