https://www.acmicpc.net/problem/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/
해당 블로그를 보고 공부했다.
'Algorithm > 백준' 카테고리의 다른 글
[Python] 백준 10819번 - 차이를 최대로(실버2) (0) | 2023.08.01 |
---|---|
[Python] 백준 11722번 - 가장 긴 감소하는 부분 수열 (실버2) (0) | 2023.07.31 |
[Python] 백준 2644번 - 촌수계산 (0) | 2023.07.28 |
[Python] 백준 10844번 - 쉬운 계단 수 (0) | 2023.07.27 |
[Python] 백준 11729번 - 하노이 탑 이동 순서 (0) | 2023.07.26 |
댓글