이 문제에서는 N개의 정수로 이루어진 배열과 숫자 K가 주어집니다. 우리의 목표는 배열에서 임의의 K개 요소를 선택하여 더함으로써 만들 수 있는 모든 고유한(distinct) 숫자를 출력하는 것입니다. 단, 같은 숫자를 최대 K번까지 반복해서 선택할 수도 있습니다.
문제 이해를 위한 예시
예제를 통해 문제를 자세히 살펴보겠습니다.
입력: array = {2, 5, 13, 9}, K = 2
출력: 4, 7, 10, 11, 14, 15, 18, 22, 26
설명: 두 개의 요소를 더한 경우:
2+2=4, 2+5=7, 2+13=15, 2+9=11,
5+5=10, 5+13=18, 5+9=14,
13+13=26, 13+9=22, 9+9=18위 예시에서 볼 수 있듯이, 동일한 요소를 두 번 더하는 경우도 허용되며, 중복된 합계 값은 한 번만 출력됩니다.
접근 방법
이 문제를 해결하려면 배열에서 K개 요소로 만들 수 있는 모든 조합을 찾아야 합니다. 이를 위해 다음과 같은 전략을 사용합니다.
- 재귀 호출을 사용하여 K개 요소의 모든 조합을 생성하고 각 단계마다 누적 합계를 계산합니다.
- 중복된 값을 제거하기 위해 생성된 숫자들을 set에 저장합니다. set은 자동으로 중복을 제거하고 오름차순으로 정렬해 주므로 결과 출력에도 유리합니다.
재귀의 깊이가 K에 도달하면 현재까지의 합계를 set에 삽입하고 탐색을 종료합니다. 시간 복잡도는 대략 O(n^k)이며, n은 배열의 크기입니다.
구현 예제
다음 코드는 위 해결 방법의 C++ 구현을 보여줍니다.
#include <bits/stdc++.h>
using namespace std;
set<int> distNumbers;
void generateNumberFromArray(int count, int arr[], int n, int num, int k) {
if (k == count) {
distNumbers.insert(num);
return;
}
for (int i = 0; i < n; i++) {
generateNumberFromArray(count + 1, arr, n, num + arr[i], k);
}
}
void printDistinctIntegers(int k, int arr[], int n) {
generateNumberFromArray(0, arr, n, 0, k);
cout<<"The "<<distNumbers.size()<<" distinct integers are:\n";
while (!distNumbers.empty()) {
cout << *distNumbers.begin() <<"\t";
distNumbers.erase(*distNumbers.begin());
}
}
int main() {
int arr[]={ 2, 5, 13, 9 };
int n=4;
int k=2;
printDistinctIntegers(k, arr, n);
return 0;
}
코드 설명
generateNumberFromArray 함수는 현재까지 선택한 요소의 개수(count)와 누적 합계(num)를 인자로 받습니다. count가 K에 도달하면 합계를 set에 저장하고 반환하며, 그렇지 않으면 배열의 모든 요소를 하나씩 더하며 재귀 호출을 이어갑니다. 이 과정에서 같은 요소를 여러 번 선택하는 것도 자연스럽게 처리됩니다.
출력 결과
The 9 distinct integers are −
4 7 10 11 14 15 18 22 26
실행 결과 총 9개의 고유한 정수가 오름차순으로 출력되는 것을 확인할 수 있습니다. set 자료구조 덕분에 중복 제거와 정렬이 자동으로 처리되어 코드가 간결해집니다.