[DP] 백준 1699 제곱수의 합 python

📄 백준 1699 제곱수의 합 📄

www.acmicpc.net/problem/1699

1699번: 제곱수의 합

---

🤔 문제 풀이  🤔

숫자가 주어질 때 제곱수의 합으로 나타낼 수 있는 최소 항의  갯수를 구하는 문제이다.

 

먼저 모든 숫자는 1의 제곱으로 만들 수 있으며 그 때 항의 갯수는 숫자 n일 때 n개 이다.

 

이제 1부터 n까지 숫자를 증가시켜가면서 각각의 숫자에 대해 최소항의 갯수를 구해보자.

1일 때는 1개이다.

2일 때는 1^2, 1^2 2개이다.

3일 때는 3개

 

4일 때는 (1^2 ) * 4 4개도 되나 4보다 작은 수 중 가능한 모든 제곱수를 만들어보면 "2^2 = 4"이므로 1개이다.
dp[4] = min(dp[4], dp[4 - (2^2)])

 

이렇게 n까지 진행하면 각각의 단계에서 현재 값의 최소항의 갯수를 계산하게 된다.

각각의 단계에서 구한 이 최소항의 갯수를 이용해 우리가 원하는 n의 최소항의 갯수를 구해낼 수 있다.

 

---

⌨️ 코드 ⌨️

import math

n = int(input())

dp = [0] * (n + 1)

for i in range(1, n + 1):
    dp[i] = i
    for j in range(1, int(math.sqrt(i)) + 1):
        dp[i] = min(dp[i], dp[i - j * j] + 1)

print(dp[n])