문제 이해 단계
모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다.
자연수 n이 주어질 때, 최소 개수의 제곱수 합,
즉 최소한의 자연수를 사용하여 구하는 문제이다.
문제 접근 단계
제곱수라는 말과 반대되는 말은 루트이다.
4 = 2^2인데, 이때 제곱이 되는 2라는 값은 4의 루트를 씌우면 구할 수 있다.
여기서 5라는 값을 살펴보면
5의 루트를 씌우면 2.xxx 자연수 부분은 2가 된다.
해당 문제에서는
5 = 2^2 + 1^2가 되어 2가 출력될 것이다.
이런 식으로 n에다가 루트를 씌어 하나의 제곱수를 구하고,
그 수를 뺀 나머지를 또 루트를 씌우는 과정을 반복한다면?
우리는 제곱으로만 이루어진 수의 합을 구할 수 있을 것이다(1^2이 있기 때문)
15라는 숫자를 예로 들어, 그림으로 나타내보면 이런 식이 된다.
15의 루트를 씌우면 3의 제곱과 나머지 6이 나온다.
또 6의 루트를 씌우면 2의 제곱과 나머지 2가 나온다.
2는 1^2+1^2이므로 계산해 보면
저런 식으로 답을 도출할 수 있다.
그런데 그게 최소 개수라고 확신할 수는 없을 것이다.
12라는 수를 생각해 보자.
저런 식으로 계산한다면,
12 = 3^2 + 1^2 + 1^2 + 1^2으로 4가 나오는데,
다른 경우로 12 = 2^2 + 2^2 + 2^2를 하면
3이 나오므로 더 작은 경우가 존재한다.
즉, n에다가 루트를 씌운 것은 최대 개수이기 때문에
1씩 빼가면서 모든 경우를 순차적으로 찾아봐야 한다.
이런 식으로 재귀함수를 구성할 수 있다.
그런데 만약 값의 저장 없이 값을 구할 때마다 계속 반복한다면
틀림없이 시간초과가 뜨거나, 연산과정이 오래 걸릴 것이다.
그래서 각 숫자마다 연산 결과 즉, 최소 개수를 저장해 두어,
다른 연산에서 필요할 때마다 사용할 것이다.
즉, 다이내믹 프로그래밍 기법을 사용하여 문제를 풀 것이다.
자세한 것은 코드를 통해 설명하겠다.
문제 구현 단계
int d[50001];
#define MAX 99999
int dp(int x, int depth) {
if (x == 0) return 0;
; if (x == 1) return 1;
if (d[x] != 0) return d[x];
int key = (int)sqrt(x);
int answer = MAX;
for (int i = key; i > 0; i--) {
int value = dp(x - i * i, depth + 1);
if (value >= MAX) continue;
answer = min(answer, 1 + value);
}
return d[x] = answer;
}핵심이 되는 dp함수이다.
매개변수로 정수 x와 제곱수의 밑을 뜻하는 depth를 받는다.
최대 50000까지 들어올 수 있으니
인덱스를 50000까지 받을 수 있도록 배열을 설정해 두고,
x값이 0과 1일 때의 값을 처리해 준다.
또한 이미 저장된 배열일 경우, 그 값을 return 해줘 연산 속도를 줄여준다.
위에서 설명했듯 해당 x값에 루트를 씌운 후,
그것을 int형으로 바꾸면 자연스레 소수점을 버려진다.
그 값을 변수 key로 잡고, 그 key값에서 1씩 빼가면서 재귀호출을 반복한다.
그중에서 가장 depth가 가장 작은 경우가 그 d [x]의 값이 된다.
여기서 MAX를 99999로 정의해 준 이유는, min을 해주는 것이기 때문이다.
그러니까, 최초의 나온 값이 무조건 뽑히게 하기 위해서이다.
핵심코드는 여기가 끝이고,
마지막으로 전체 코드에 대해서 설명하고 끝내겠다.
#include <iostream>
#include <cmath>
using namespace std;
int d[50001];
#define MAX 99999
int dp(int x, int depth) {
if (x == 0) return 0;
; if (x == 1) return 1;
if (d[x] != 0) return d[x];
int key = (int)sqrt(x);
int answer = MAX;
for (int i = key; i > 0; i--) {
int value = dp(x - i * i, depth + 1);
if (value >= MAX) continue;
answer = min(answer, 1 + value);
}
return d[x] = answer;
}
int main() {
cin.tie(0);
cout.tie(0);
ios::sync_with_stdio(false);
d[0] = 0;
d[1] = 1;
int n;
cin >> n;
cout << dp(n, 0);
}d [0]과 d [1]에는 값을 넣어준 후, 입력받은 n에 함수 dp를 실행한다.
여기서 depth는 아무것도 하지 않은 상태이기 때문에 0으로 설정해 둔다.
시행착오
처음에는 루트를 씌어서 자연수 부분을 쓰고
나머지 부분에 또 루트를 씌어서 재귀함수를 쓰면 될 줄 알았다.
그렇게 하면 답이 될 줄 알았는데 예외케이스가 계속 생겨서,
그냥 저 방법 자체가 아닌 줄 알았다.
왜냐하면 Key값부터 1씩 작아지면서 계속 반복을 해야 해서
시간초과가 뜰 것 같았기 때문이다.
근데 곰곰이 생각해 보니 줄어드는 비율이 루트 씩 작아지니까
시간 초과가 뜰 리가 없겠다 싶어서
저렇게 풀이해 보니까 바로 맞더라.
역시 시간 계산에 대해서 공부할 필요가 있어 보인다.