문제
라그랑주는 1770년에 모든 자연수는 넷 혹은 그 이하의 제곱수의 합으로 표현할 수 있다고 증명하였다. 어떤 자연수는 복수의 방법으로 표현된다. 예를 들면, 26은 5^2과 1^2의 합이다; 또한 4^2 + 3^2 + 1^2으로 표현할 수도 있다. 역사적으로 암산의 명수들에게 공통적으로 주어지는 문제가 바로 자연수를 넷 혹은 그 이하의 제곱수 합으로 나타내라는 것이었다. 1900년대 초반에 한 암산가가 15663 = 125^2 + 6^2 + 1^2 + 1^2라는 해를 구하는데 8초가 걸렸다는 보고가 있다. 좀 더 어려운 문제에 대해서는 56초가 걸렸다: 11339 = 105^2 + 15^2 + 8^2 + 5^2.
자연수 n이 주어질 때, n을 최소 개수의 제곱수 합으로 표현하는 컴퓨터 프로그램을 작성하시오.
입력
입력은 표준입력을 사용한다. 입력은 자연수 n을 포함하는 한 줄로 구성된다. 여기서, 1 ≤ n ≤ 50,000이다.
출력
출력은 표준출력을 사용한다. 합이 n과 같게 되는 제곱수들의 최소 개수를 한 줄에 출력한다.
풀이
어떤 수를 제곱수 몇 개의 합으로 만들 수 있는지 묻는 문제라서, 작은 수부터 최소 개수를 DP로 쌓아 가면 된다. i를 만들 때는 i - j^2를 만들던 최소 개수에 1을 더하는 식으로 볼 수 있다.
코드에서는 현재 수보다 작거나 같은 제곱수들을 모두 시도하면서 최솟값을 갱신한다. 가능한 마지막 제곱수를 하나 정하고, 나머지를 이전 상태에 맡기는 구조다.
직접 조합을 만들기보다 마지막에 어떤 제곱수를 썼는가로 전이를 세우는 것이 핵심이다. 작은 값부터 채우면 큰 값도 자연스럽게 결정된다.
코드
#include <iostream>
using namespace std;
int arr[50001];
void solve() {
int n;
cin >> n;
arr[1] = 1;
for (int i = 2; i <= n; i++) {
arr[i] = arr[i - 1] + 1;
for (int j = 1; j * j <= i; j++) {
arr[i] = min(arr[i], arr[i - j * j] + 1);
}
}
cout << arr[n] << '\n';
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
solve();
return 0;
}복잡도
- 시간 복잡도: 각 수마다 가능한 제곱수를 확인하므로 이다.
- 공간 복잡도: DP 배열을 저장하므로 이다.
마무리
각 수를 제곱수 몇 개의 합으로 만들 수 있는지 차근차근 갱신하면 최소 개수가 나온다.
