백준 온라인 저지의 1699번 제곱수의 합 문제입니다.
[링크] https://www.acmicpc.net/problem/1699
문제 조건과 설명
- 어떤 자연수 N은 그보다 작거나 같은 제곱수들의 합으로 나타낼 수 있습니다.
- 예를 들어, 11 = 3²+1²+1² 으로 3개 항의 제곱수들의 합으로 나타낼 수 있습니다.
- 하지만, 11 = 2²+2²+1²+1²+1² 으로 5개 항으로도 나타낼 수 있습니다.
- 이처럼 어떤 자연수 N을 제곱수들의 합으로 표현할 때 그 항의 최소 개수를 구해야 합니다.
- 위의 예시에서 11은 3개 항으로 나타낼 때가 최소입니다.
Input
첫째 줄에는 1<=N<=100,000 인 자연수 N이 주어집니다.
Output
주어진 자연수를 제곱수의 합으로 나타낼 때, 그 제곱수 항의 최소 개수를 출력합니다.
생각한 아이디어
DP를 풀 때 정말 단순한 생각만 가지고는 해결하기 힘들다는 것을 알게 해 준 문제였습니다.
그리고 문제를 많이 풀어보고 수학적으로 여러 방법으로도 생각해 봐야 할 것 같습니다.
막상 그 규칙을 찾으면 소스 코드의 길이는 길지 않았지만, 여기까지 오는데 많이 어려움을 느꼈던 문제였습니다.
- 자연수 1부터 차례대로 살펴보겠습니다. -> 1 = 1² = 항 1개
- 자연수 2는 1² + 1² 으로 항 2개로 나타낼 수 있고 이것이 최소 길이입니다.
- 자연수 3도 1² + 1² + 1² 으로 항 3개로 나타낼 수 있으며 이것이 최소 길이입니다.
- 자연수 4는 1² + 1² + 1² + 1² 으로 나타낼 수도 있지만, 2² 의 항 1개로 나타낼 수 있습니다.
- 그러면 조금 건너뛰어 자연수 7을 살펴보겠습니다.
- 7은 1²을 7번 더할 수도 있지만, 7보다 작은 자연수들 중 제곱수인 2² 을 포함시킨다면 2² + 1² + 1² + 1² 로 4개 항으로 나타낼 수 있습니다.
- 자연수 8은, 1²을 8번 더할 수도 있지만, 2²을 2번 더해 2개 항으로 나타낼 수 있습니다.
- 자연수 9는, 3² 의 항 1개로 나타낼 수 있습니다.
- 자연수 10은, 3² + 1² 의 항 2개로 나타낼 수 있습니다.
여기까지 살펴볼 때, 1²만으로 이루어지지 않고, 그보다 큰 제곱수들로 이루어질 수 있었던 수들을 살펴보겠습니다.
- 4 = 2²
- 7 = 2² + 1² + 1² + 1²
- 8 = 2² + 2²
- 9 = 3²
- 10 = 3² + 1²
이것들을 다시 아래와 같이 생각해볼 수 있습니다.
- 4 = (4 - 2²) + 2² … // 4에서 2²를 빼면 0이므로, 0은 제곱수의 합으로 표현할 때 항이 0개, 거기에 2²을 추가로 붙이면 항의 갯수는 1개
7 = (7 - 2²) + 2² … // 7에서 2²를 빼면 3인데, 3을 제곱수의 합으로 표현한 최소 형태의 마지막에 2² 한개를 추가로 붙인다고 생각
- 8 = (8 - 2²) + 2² … // 8에서 2²을 빼면 4인데, 4를 제곱수의 합으로 표현한 최소 형태의 마지막에 2² 한개를 추가로 붙인다고 생각
- 9 = (9 - 2²) + 2² 혹은, 9 = (9 - 3²) + 3²
- 전자의 경우, 9에서 2²을 빼면 5인데, 5를 제곱수의 합으로 표현한 최소 형태의 마지막에 2² 한개를 추가로 붙인다고 생각
- 후자의 경우, 9에서 3²을 빼면 0이므로, 0은 제곱수의 합으로 표현할 때 항이 0개, 거기에 3² 한개를 추가로 붙이면 항의 갯수는 1개
- 전자와 후자 중 최소를 고른다. → 9는 제곱수의 항 1개로 표현 가능
9에서는 2²을 빼는 경우와 3²을 빼는 경우로 추가로 나뉘었음을 알 수 있습니다..
그러면 더 큰 수인 43을 확인해 볼까요?
- 43 = (43 - 2²) + 2² = …
- = (43 - 3²) + 3² = …
- = (43 - 4²) + 4² = …
- = (43 - 5²) + 5² = 18 + 5² -> 18은 3² + 3² = 2개의 최소 항으로 표시 -> 총 항의 갯수 3개
- 43 = 18 + 5² = 3² + 3²+5² (3개)
- = (43 - 6²) + 6² = 7 + 6² -> 7은 1² + 1² + 1² + 2² = 4개의 최소 항으로 표시 -> 총 항의 갯수 5개
- 43 = 7 + 6² = 1² + 1² + 1² + 2²+6² (5개)
- [참고] 위의 예시처럼, 더 큰 제곱수를 뺀다 해도, 반드시 최소 항의 갯수를 구한다고 보장할 수 없습니다.
- 43에서 36을 뺐을 때가 아닌, 25를 뺐을 때 최소 항의 갯수 3개를 가집니다.
- 따라서 단순하게 자연수 N보다 작은 제곱수들 중 가장 큰 것으로만 빼서 계산한다면 틀리게 됩니다.
- 그러므로 위와 같은 전체적인 과정을 모두 담아야 합니다.
[정리] 위 과정들을 단순화하면 다음과 같습니다.
- (1) dp[N]은 어떤 자연수 N을 제곱수의 합으로 나타낼 때 항의 최소 개수를 말한다.
- (2) 처음에는 모든 수들을 1²의 합으로 나타낸다고 생각하고 dp[N] = N 으로 초기화해 놓는다.
- (3) 어떤 자연수 N에 대해, N=1부터 시작하면서 N보다 작은 제곱수를 가장 작은 것부터 뺀다.
- (3-1) 빼서 나온 그 수(N - 제곱수)를 제곱수들의 합으로 나타낼 때의 항의 최소 개수는 dp[N - 제곱수]이며, 여기에 제곱수 1개 항을 추가로 붙여줬을 때 총 항의 갯수는 dp[N - 제곱수] + 1 이다.
- (예) 11에서 3²을 뺐을 때 dp[11 - 3²] = dp[2] 이며, 여기에 제곱수 1개인 3²을 추가로 더해주는 것.
총 항의 갯수는 dp[N-제곱수] + 1 = dp[11-3²] + 1 = dp[2] + 1 = 3 이 된다.
- 11 = (11 - 3²) + 3² = 1² + 1² + 3² (항 3개)
- (4) dp[N-제곱수]+1과 기존의 dp[N]과 비교해 더 작은 값을 dp[N]에 대입한다.
1
dp[N] = min(dp[N], dp[N - 제곱수] + 1)
- 다시 (3)의 과정으로 가서 그 다음 제곱수를 빼고 과정을 반복한다.
- 정리하여 말하자면, 자연수 32를 예로 들었을 때
- dp[32-1²], dp[32-2²], dp[32-3²], dp[32-4²], dp[32-5²] 중에서 최솟값에 +1을 하면 정답이 됩니다.
- dp 배열을 형성하기 위해, 1부터 N까지 bottom-up 으로 반복합니다. 이전 dp 값들이 이후의 값 계산에 쓰일 수 있습니다.
- 따라서 어떤 자연수 N에 대해 최소 항의 갯수는 다음과 같이 구할 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
// 초기 모든 자연수 N들은 1²의 합들로 초기화 해 놓습니다.
// 예를 들어, 자연수 i는 1² 을 i번 더하므로 dp[i] = i으로 초기화합니다.
for (int i = 0; i <= N; i++)
dp[i] = i;
// 이후, i보다 작은 제곱수들로 i에서 뺀 다음, 그 수의 dp 배열값을 활용해 아래와 같이 구합니다.
for (int i = 1; i <= N; i++) {
for (int j = 1; j * j <= i; j++) {
dp[i] = min(dp[i], dp[i - j * j] + 1);
}
}
설명이 다소 장황할 수 있지만 생각하면 이보다 짧은 내용으로 정리할 수 있다고 생각합니다.
처음부터 이런 생각을 어떻게 할 지 자세히 적다 보니 길어진 것 같습니다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int dp[100001];
int main() {
int N;
scanf("%d", &N);
dp[0] = 0; dp[1] = 1;
for (int i = 0; i <= N; i++)
dp[i] = i;
for (int i = 1; i <= N; i++) {
for (int j = 1; j * j <= i; j++) {
dp[i] = min(dp[i], dp[i - j * j] + 1);
// 이후 j의 반복이 계속되어, 기존 dp[i]의 값과 새로운 dp[i - j * j] + 1
// 과의 비교를 하려면 min 의 인자에 들어갈 두 값들은 위와 같다.
}
}
printf("%d",dp[N]);
}