문제 개요
모든 자연수는 하나 이상의 완전제곱수(1, 4, 9, 16, 25, ...)의 합으로 표현할 수 있습니다. 이 문제에서는 주어진 값을 완전제곱수의 합으로 나타낼 때 필요한 항의 최소 개수를 구해야 합니다.
예를 들어 값이 95라면 다음과 같이 네 개의 제곱수로 표현할 수 있으므로 답은 4가 됩니다.
95 = 92 + 32 + 22 + 12
문제를 해결하는 기본 아이디어는 1부터 시작하여 점차 더 큰 완전제곱수를 차례로 살펴보는 것입니다. 값이 1부터 3 사이일 때는 반드시 1만을 사용해 표현해야 하므로, 각각 1개, 2개, 3개의 항이 필요합니다.
입력 및 출력
입력: 정수 하나. 예를 들어 63. 출력: 필요한 제곱수 항의 개수. 여기서는 4입니다. 63 = 72 + 32 + 22 + 1
알고리즘
minSquareTerms(value)
입력: 주어진 값.
출력: 해당 값을 만들기 위해 필요한 최소 제곱수 항의 개수.
시작 크기가 (value + 1)인 배열 sqList를 선언한다. sqList[0] := 0, sqList[1] := 1, sqList[2] := 2, sqList[3] := 3 i를 4부터 n까지 반복한다. sqList[i] := i x를 1부터 i까지 반복한다. temp := x^2 만약 temp > i이면 반복문을 종료한다. 그렇지 않으면 sqList[i] := sqList[i]와 (1 + sqList[i - temp]) 중 최솟값 반복 끝 반복 끝 sqList[n]을 반환한다. 끝
이 알고리즘은 동적 계획법(Dynamic Programming)에 기반합니다. 배열 sqList[i]에는 "값 i를 표현하는 데 필요한 최소 제곱수 항의 개수"가 저장됩니다. 각 값 i에 대해 i 이하의 모든 제곱수 x²을 하나의 항으로 사용해 보고, 남은 값 (i − x²)에 대한 최소 항 개수에 1을 더한 값들 중 가장 작은 것을 선택합니다.
예제 코드 (C++)
#include<bits/stdc++.h>
using namespace std;
int min(int x, int y) {
return (x < y)? x: y;
}
int minSquareTerms(int n) {
int *squareList = new int[n+1];
//0부터 3까지는 모두 1²로만 표현해야 합니다.
squareList[0] = 0;
squareList[1] = 1;
squareList[2] = 2;
squareList[3] = 3;
for (int i = 4; i <= n; i++) {
squareList[i] = i; //초기에는 최대값인 i를 저장합니다.
for (int x = 1; x <= i; x++) {
int temp = x*x; //i 이하의 제곱수 항을 찾습니다.
if (temp > i)
break;
else squareList[i] = min(squareList[i], 1+squareList[i-temp]);
}
}
return squareList[n];
}
int main() {
int n;
cout << "숫자를 입력하세요: "; cin >> n;
cout << "필요한 최소 제곱수 항의 개수: " << minSquareTerms(n);
return 0;
}실행 결과
숫자를 입력하세요: 63 필요한 최소 제곱수 항의 개수: 4
복잡도 분석
바깥쪽 반복문이 n번, 안쪽 반복문이 최대 √n번 실행되므로 전체 시간 복잡도는 O(n√n)입니다. 크기가 n+1인 배열 하나만 사용하므로 공간 복잡도는 O(n)입니다.