[백준] 1699번 : 제곱수의 합 (Python)

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

 

 

자연수 N을 제곱수들의 합으로 표현할 때, 

그 항의 최소개수를 구하는 문제.

 

import sys

input = sys.stdin.readline

N = int(input()) # 자연수 N
DP = [sys.maxsize]*(100001)
DP[0] = 0
DP[1] = 1

for i in range(2, N+1):
    
    sqrt = int(i**(1/2)) # 제곱근
    
    if(i == sqrt**2):
        DP[i] = 1 # 제곱일 경우엔 1
        continue

    for j in range(sqrt//2, sqrt+1):
        DP[i] = min(DP[i], DP[i-(j**2)]+1) # 최소값 찾기

    
print(DP[N])

 

 

 

[문제풀이]

---

 

이 문제는 동적 계획법, 즉 DP를 이용해서 풀 수 있다.