양의 정수 n이 주어졌을 때, 그 합이 정확히 n이 되도록 만드는 완전 제곱수(perfect square)의 최소 개수를 구하는 문제입니다. 예를 들어 n이 13이라면 13 = 9 + 4로 표현할 수 있으므로, 필요한 완전 제곱수의 개수는 2개입니다.
문제 접근 방법
이 문제는 동적 계획법(Dynamic Programming)을 활용하면 효율적으로 해결할 수 있습니다. 핵심 아이디어는 'j를 만들기 위해 필요한 최소 완전 제곱수의 개수'를 작은 값부터 차례로 계산해 나가는 것입니다. 알고리즘의 단계는 다음과 같습니다.
- 길이가 n + 1인 동적 계획법용 테이블(dp)을 생성하고, 모든 값을 무한대(INF)로 초기화합니다.
- dp[0] := 0 으로 설정합니다. (0을 만드는 데 필요한 제곱수의 개수는 0개)
- i := 1부터 시작하여 i*i <= n을 만족하는 동안 반복합니다.
- x = i * i 로 설정합니다.
- j := x 부터 n 까지 반복하면서 dp[j] := min(dp[j], 1 + dp[j – x]) 로 갱신합니다.
- 최종 결과로 dp[n]을 반환합니다.
즉, 각 완전 제곱수 x를 하나 사용했을 때 나머지 값(j – x)을 만드는 최적의 해에 1을 더한 것과 기존 값을 비교하여 더 작은 값으로 갱신하는 방식입니다.
C++ 구현 예제
아래 코드를 통해 실제 구현 방법을 더 자세히 이해해 보겠습니다.
#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
class Solution {
public:
int numSquares(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.numSquares(147));
}입력
147
출력
3
결과 해석
n = 147인 경우 출력값은 3입니다. 이는 147 = 49 + 49 + 49, 즉 7² + 7² + 7²로 세 개의 완전 제곱수만으로 표현할 수 있기 때문입니다. 두 개 이하의 완전 제곱수로는 147을 만들 수 없으므로, 최솟값 3이 올바른 답이 됩니다.