[맛있는물회] <백준 알고리즘> 1699번 " 제곱수의 합"

문제 조건

---

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

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

 

Input

---

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

 

Output

---

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

 

생각한 아이디어

---

디피 넘모 어려웡,, ㅠㅠ

0 - 0개

1 - 1^2 (1개)
2 - 1^2 + 1^2 (2개)
3 - 1^2 + 1^2 + 1^2 (3개)
4 - 2^2 (1개)
5 - 2^2 + 1^2 (2개)
6 - 2^2 + 1^2 + 1^2 (3개)
7 - 2^2 + 1^2 + 1^2 + 1^2 (4개)
8 - 2^2 + 2^2 (2개)
9 - 3^2 (1개)
10 - 3^2 + 1^2 (2개)
11 - 3^2 + 1^2 + 1^2 (3개)
12 - 3^2 + 1^2 + 1^2 + 1^2 (4개)
13 - 3^2 + 2^2 (2개)
14 - 3^2 + 2^2 + 1^2 (3개)
15 - 3^2 + 2^2 + 1^2 + 1^2 (4개)
16 - 4^2 (1개)

단순하게 가장 큰 제곱수를 기준으로 진행하다가 

18을 만났다..

18은 4^2 + 1 + 1도 가능하지만

3^2 + 3^2 로 더 짧게도 가능하다.

 

디피라서 완전 쉬운 점화식으로 끝날 줄 알았지만 생각보다 시간초과 기준이 길어서 괜찮았던 것 같다.

n이 주어지면 n보다 작게 모든 제곱수를 빼보면서 최솟값을 찾는 것이다.

18일때 4로 빼서 dp[16]과 , 3의 제곱을 빼서 dp[9]를 비교해보면서 쭉쭉나가면 코드는 쉽게 짜진다. 

 

디피도 바로바로 해결안되는 것도 있구나 라고 알게되었다!

 

소스코드

#1699 제곱수의 합
n=int(input())
dp=[0,1]
for i in range(2,n+1):
   idx=1
   MIN=i
   while 1:
      if i >= idx**2:
         MIN=min(MIN,dp[i-idx**2])
      else: break
      idx += 1
   dp.append(MIN+1)
print(dp[n])

 

*파이썬 문법 정리