양의 정수 n이 주어졌을 때, 그 합이 정확히 n이 되도록 하는 완전제곱수(perfect square)의 최소 개수를 구하는 문제입니다. 예를 들어 n이 10이라면, 10 = 9 + 1처럼 두 개의 완전제곱수로 표현할 수 있으므로 출력은 2가 됩니다.
이 문제는 동적 프로그래밍(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 해결 절차는 다음과 같습니다.
- 길이가 n + 1인 DP 테이블을 생성하고, 모든 값을 무한대(INF)로 초기화합니다.
- dp[0] := 0 으로 설정합니다. (합이 0이 되는 데 필요한 완전제곱수의 개수는 0개)
- i := 1부터 시작하여 i * i <= n을 만족하는 동안 반복합니다.
- x = i * i 로 현재 완전제곱수를 구합니다.
- j를 x부터 n까지 반복하면서 다음 점화식을 적용합니다.
- dp[j] := dp[j]와 1 + dp[j − x] 중 더 작은 값
- 최종적으로 dp[n]을 반환합니다.
동작 원리 이해하기
dp[j]는 "합이 j가 되기 위해 필요한 완전제곱수의 최소 개수"를 의미합니다. 각 완전제곱수 x = i²에 대해, j에서 x를 하나 빼면 남은 값(j − x)의 최소 개수에 1을 더한 것이 후보가 됩니다. 이 과정을 모든 가능한 완전제곱수에 대해 반복하면 dp[n]에 최종 답이 저장됩니다.
다음 구현 예시를 통해 더 자세히 살펴보겠습니다.
예제 코드
#include<bits/stdc++.h>
using namespace std;
#define INF 1e9
class Solution {
public:
int solve(int n) {
vector<int> dp(n+1, INF);
dp[0] = 0;
for(int i = 1; i*i <= n; i++){
int x = i*i;
for(int j = x; j <= n; j++){
dp[j] = min(dp[j], 1 + dp[j-x]);
}
}
return dp[n];
}
};
main(){
Solution ob;
cout << ob.solve(10);
}입력
10
출력
2
위 코드에서 n = 10일 때, 사용 가능한 완전제곱수는 1, 4, 9입니다. 9와 1을 조합하면 두 개의 완전제곱수로 10을 만들 수 있으므로 결과값으로 2가 출력됩니다. 이 알고리즘의 시간 복잡도는 O(n × √n)이며, 공간 복잡도는 O(n)입니다.