[백준] 1699번 제곱수의 합 - Python / 알고리즘 기초 1/2 - 다이나믹 프로그래밍 1

---

---

---

💡 문제

어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있다. 예를 들어 11=3$^2$+1$^2$+1$^2$(3개 항)이다. 이런 표현방법은 여러 가지가 될 수 있는데, 11의 경우 11=2$^2$+2$^2$+1$^2$+1$^2$+1$^2$(5개 항)도 가능하다. 이 경우, 수학자 숌크라테스는 “11은 3개 항의 제곱수 합으로 표현할 수 있다.”라고 말한다. 또한 11은 그보다 적은 항의 제곱수 합으로 표현할 수 없으므로, 11을 그 합으로써 표현할 수 있는 제곱수 항의 최소 개수는 3이다.

주어진 자연수 N을 이렇게 제곱수들의 합으로 표현할 때에 그 항의 최소개수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 자연수 N이 주어진다. (1 ≤ N ≤ 100,000)

출력

주어진 자연수를 제곱수의 합으로 나타낼 때에 그 제곱수 항의 최소 개수를 출력한다.

---

💭 접근

1. 우선 모든 제곱수의 합은 1$^2$로 이루어진 합이 최대이기 때문에 dp를 1~n으로 초기화해준다.
2. 이후, i는 n까지, j는 $\sqrt{i}$까지 dp[i - j * j]를 반복하며 가장 작은 수에 +1한 값을 저장해준다.

ex) n = 8
dp = [0, 1, 2, 3, 1, 2, 3, 4, 8] (i = 7까지의 과정은 생략)
i = 8, j = 0 -> dp[8 - 0 * 0] + 1 = dp[8] + 1 = 9
i = 8, j = 1 -> dp[8 - 1 * 1] + 1 = dp[7] + 1 = 8
i = 8, j = 2 -> dp[8 - 2 * 2] + 1 = dp[4] + 1 = 2
-> dp = [0, 1, 2, 3, 1, 2, 3, 4, 2]

---

📒 코드

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

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

print(dp[n])

---

💭 후기

처음 이 문제를 봤을 땐 i - 1번째에 1을 더한 수와 비교를 하며 나아가야 할 것 같은데, 4, 9, 16과 같은 제곱수들을 1로 저장하는 방법을 찾는데에서 많이 헤맸다.
그러다, 2중 for문을 사용하여 각 수들의 $\sqrt{i}$까지 반복하며 비교하면 될 것같다는 생각을 하고, 문제를 해결하였다.

---

🔗 문제 출처

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

---