[Python] 백준 1699번 - 제곱수의 합(실버2)

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

1699번: 제곱수의 합

 

혼자 힘으로 풀었는가? X

알고리즘 분류
 - 수학
 - 다이나믹 프로그래밍

 

문제

어떤 자연수 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)

출력

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

 

---

 

보자마자 이건 DP문제다! 싶었는데

 

어떻게 식을 구해내는지를 찾을수가 없었다.

 

우선 나는 각 숫자별로 항의 최소개수를 구해보았다.

 

 

여기서 12를 주목해보자.

 

12는 단순히 생각했을 때

 

$ 3^2 + 1^2 + 1^2 + 1^2 $으로 최소 항이 4개일 것 같다.

 

하지만

 

$ 2^2 + 2^2 + 2^2$ 으로 3개의 최소항을 갖는다.

 

이처럼 수가 반드시 큰 게 최소 항을 갖는 것이 아님을 알게 되었다.

 

즉 이 문제를 풀기 위해선 어느 정도 반복이 필요하다는 것을 알았고 이 반복을 최소화하기 위해

 

DP의 메모이제이션기법으로 풀어나갈 것이다.

 

---

일단 해야 할 일들은

 

1. 반복문을 통해 최소항의 조건을 전부 확인한다.

 

2. 메모이제이션을 사용한다.

 

이렇게 두 가지로 우선 $1^2$만 더해진 수를 각 DP[n] = n으로 초기화한다.

그다음 1부터 DP[n]의 n이 되는 제곱 수 까지 반복문을 돌리면서 DP를 채워준다.

 

예를 들어 DP[1 ~ 3] 은  각 1, 2, 3이다.

 

DP[1] = DP[1-1] + 1 = 0 + 1 = 1

DP[2] = DP[2-1] + 1 = 1 + 1 = 2

DP[3] = DP[3-1] + 1 = 2 + 1 = 3

 

이후 DP[4]를 보면

DP[4] = DP[4-1] +1 = DP[3] + 1 = 3 + 1 = 4

 

위의 결과는

 

$ 4 = 1^2 + 1^2 + 1^2 + 1^2$

라는 결과물이다.

 

하지만 여기서 반복문이 한번 더 돌수 있다.

 

DP[4] = DP[$4 - 2^2$] + 1 = DP[0] + 1 = 1

 -> $4 = 2^2 + 2^2$

 

여기까지 본 사람들은 왜 항상 +1을 해주는지 의문을 가질 텐데

예를 들어 DP[11]을 예시로 들면

 

$ 11 = 3^2 + 1^2 + 1^2$ 이 된다.

 

여기서 $ 1^2 + 1^2$이 무엇인지 나타내는 수가 있다.

 

바로 DP[2]이다. 그래서 DP[2] + 1을 해주면 11이 되는 것이다.

 

이를 좀 더 보기 쉽게 코드처럼 나타낸다면

 

DP [12]는 아래와 같이 나타낼 수 있고

 

 

 

DP[13]

 

import sys
import math
input = sys.stdin.readline

n = int(input())
dp = []

#dp[n] = n 으로 초기화
for i in range(n+1):
    dp.append(i)
    
for i in range(1, n+1):
    for j in range(1, i):
        if j*j > i:
            break
        dp[i] = min(dp[i], dp[i-j*j]+1)
print(dp[n])

 

어려운 문제이다.

 

혼자서는 절대 생각 못한다...

 

https://chanhuiseok.github.io/posts/baek-10/

[백준] 1699번 - 제곱수의 합

해당 블로그를 보고 공부했다.