어떤 수 N과 또 다른 수 k가 주어졌을 때, N을 1보다 큰 k개의 수의 곱으로 표현할 수 있는지 확인하는 문제입니다. 예를 들어 N = 54, k = 3이라면 [2, 3, 9]와 같이 세 개의 수로 표현할 수 있습니다. 반면 표현이 불가능한 경우에는 그 사실을 출력해야 합니다.
접근 방법
이 문제는 소인수분해를 활용하여 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- N의 모든 소인수를 구하여 벡터(vector)에 저장합니다.
- 1보다 큰 k개의 수를 만들 수 있는지 확인하기 위해 벡터의 크기가 k 이상인지 검사합니다.
- 벡터의 크기가 k보다 작으면 k개의 수로 분해할 수 없으므로 -1을 반환합니다.
- 크기가 k 이상이면 처음 k-1개의 소인수를 그대로 출력하고, 마지막 수는 나머지 소인수들을 모두 곱한 값으로 만듭니다.
예를 들어 54는 2 × 3 × 3 × 3으로 소인수분해되므로, k = 3일 때 첫 두 소인수 2와 3을 출력하고 나머지 3 × 3 = 9를 마지막 값으로 하여 [2, 3, 9]를 얻을 수 있습니다.
예제 코드
#include<iostream>
#include<vector>
#include<cmath>
using namespace std;
int getKFactors(int n, int k){
int i;
vector<int> vec;
// 2로 나누어 떨어지는 동안 2를 소인수로 저장
while(n % 2 == 0){
vec.push_back(2);
n = n/2; // n을 2로 나누어 줄임
}
// 홀수만 검사하기 위해 i를 2씩 증가시킴
for(i = 3; i <= sqrt(n); i=i+2){
while(n % i == 0){
n = n/i;
vec.push_back(i);
}
}
if(n > 2){
vec.push_back(n);
}
// 소인수의 개수가 k보다 적으면 표현 불가
if(vec.size() < k){
cout << "Cannot be represented";
return -1;
}
// 처음 k-1개의 소인수 출력
for (int i=0; i<k-1; i++)
cout << vec[i] << ", ";
// 나머지 소인수들의 곱을 마지막 값으로 계산
int prod = 1;
for (int i=k-1; i<vec.size(); i++)
prod = prod*vec[i];
cout << prod << endl;
}
int main() {
int n = 54, k = 3;
getKFactors(n, k);
}출력 결과
2, 3, 9
위 코드에서 소인수분해는 시간 복잡도 O(√N) 안에 수행됩니다. 2를 먼저 모두 제거한 후 홀수만 검사함으로써 연산 횟수를 절반으로 줄일 수 있다는 점도 눈여겨볼 만합니다.