백준 1699번 제곱수의 합 파이썬 풀이

Python

[Python] 백준 알고리즘 온라인 저지 1699 제곱수의 합

1699 제곱수의 합

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

1699번: 제곱수의 합

어떠한 수 N이 합하여 N이 될 때 가장 큰 제곱수 자신보다 작은 수를 하나씩 늘리며 제곱해보면 찾을 수 있다.

 

알고리즘 분류

• 다이내믹 프로그래밍

 

---

소스코드

import sys
input = sys.stdin.readline

n = int(input())
dp = [k for k in range(n+1)]

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

 

---

풀이

최소의 항의 개수를 구하는 방법은 N보다 작은 가장 큰 제곱수를 구하고 뒤의 항들을 찾는 것이 가장 적은 항의 개수를 가질 수 있다.

작은 수부터 점화식을 생각해보면...

n	1	2	3	4
항	1^2	1^2+1^2	1^2+1^2+1^2	2^2

위의 표와 같은 형식을 가진다. 여기서 새로운 제곱 수가 등장할 때 1로 초기화됨을 볼 수 있다.

이를 이용하여 식을 작성하면 dp[i] = dp[i - j*j] + 1 의 형식을 가진다.

예를 들어 i = 5 라면 j는 2까지만 loop를 돌고 이전 수에 + 1^2을 더하는 방법이다. 즉 5 = 2^2 + 1^2으로 두 개의 항이 최소 항이다.

DP를 활용해 이전 수들의 항의 개수를 체크하며 dp[n]을 출력하면 된다.

 

---

풀이 결과

1699 풀이 결과