[실버 2] 백준 1699 - 제곱수의 합 (파이썬)

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

풀이

자연수 N이 주어졌을 때, N을 제곱수들의 합으로 표현하는 데에 필요한 최소 항의 수를 구하는 문제이다.

예를 들어서 4 = 2 ^ 2 → 1개, 7 = 2 ^ 2 + 1 ^ 2 + 1 ^ 2 + 1 ^ 2 → 최소 4개

D[i]를 i의 제곱수의 합으로 나타낼 수 있는 최소 항의 수라고 생각하고 문제를 푼다.

점화식은 다음과 같다.

D[i] = min(D[i], 1 + D[i - j ^ 2])

if (i ** 0.5).is_integer():
    D[i] = 1
    continue

자기 자신 하나의 제곱수로 표현 가능한 경우는 바로 1로 설정하고 넘어간다.

D[i] = 1e9  # 초기값은 매우 큰 수
j = 1
while j * j <= i / 2:
    D[i] = min(D[i], 1 + D[i - j * j])
    j += 1

i보다 작은 모둔 제곱수 j ^ 2를 고려하면서, 1 + D[i - j ^ 2] , 즉 지금 j ^ 2 하나를 쓰고, 나머지 (i - j ^ 2)는 이미 계산된 값을 사용한다

j * j ≤ i / 2 조건을 속도 향상을 위한것인데, 사실은 그냥 i까지로 해도 맞는다.

코드

# 백준 1699 - 제곱수의 합
# 분류 : 다이나믹 프로그래밍

N = int(input())

D = [0] * (N + 1)

for i in range(1, N + 1) :
    if (i ** 0.5).is_integer() :
        D[i] = 1
        continue

    D[i] = 1e9
    j = 1
    while j * j <= i / 2 :
        D[i] = min(D[i], 1 + D[i - j * j])
        j += 1
print(D[N])