개발/algorithm
[백준 17626번] Four Squares - python
zzi_on2
2022. 2. 14. 21:02
문제 링크
https://www.acmicpc.net/problem/17626
17626번: Four Squares
라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 52과 12의 합이다; 또한 42 + 32 + 1
www.acmicpc.net
풀이
- dp 문제
- dp[i] 는 i 의 최소 개수의 제곱수 합
- n보다 작거나 같은 제곱수들 i에 대해 dp[n-i*i]의 최솟값 min_value 을 구한다.
n의 최소 개수의 제곱수의 합은 선택된 제곱수 1 + n-i*i 의 최소 개수의 제곱수의 합 min_value
import sys
input = sys.stdin.readline
n = int(input())
if n == 1 or n == 2:
print(n)
else:
INF = int(1e9)
dp = [0] * (n+1)
dp[1] = 1
dp[2] = 2
# n보다 작거나 같은 최대 제곱수 1 + n과 해당 제곱수의 차이의 dp 값
for i in range(3,n+1):
min_value = INF
num = 1
# i보다 작거나 같은 최대 제곱수
while num*num <= i:
min_value = min(min_value, dp[i-num*num])
num += 1
dp[i] = 1 + min_value
print(dp[n])