문제 개요
이 문제에서는 총점 n이 주어집니다. 농구에서 얻을 수 있는 득점인 1점, 2점, 3점의 조합 중에서 합이 정확히 n이 되는 모든 경우를 출력해야 합니다.
예시를 통해 문제를 이해해 보겠습니다.
입력: 4
출력:
1 1 1 1
1 1 2
1 2 1
1 3
2 1 1
2 2
3 1
위 예시에서 총점 4를 만들 수 있는 조합은 총 7가지입니다. 순서가 다르면 서로 다른 조합으로 간주한다는 점에 유의하세요. 예를 들어 '1 1 2'와 '1 2 1', '2 1 1'은 각각 별개의 결과로 출력됩니다.
접근 방법: 재귀(Recursion) 활용
이 문제는 재귀 호출을 사용하면 깔끔하게 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.
- 현재 단계에서 1, 2, 3 중 하나의 점수 s를 선택하여 고정합니다.
- 남은 값 n - s에 대해 같은 과정을 재귀적으로 반복합니다.
- 남은 값이 0이 되면, 지금까지 선택한 점수들의 조합이 합이 n이 된 것이므로 해당 조합을 출력합니다.
이렇게 하면 가능한 모든 순열(permutation) 형태의 조합을 빠짐없이 탐색할 수 있습니다.
C++ 구현 코드
다음은 위 알고리즘을 구현한 전체 코드입니다.
#define MAX_POINT 3
#define ARR_SIZE 100
#include <bits/stdc++.h>
using namespace std;
void printScore(int arr[], int arr_size) {
int i;
for (i = 0; i < arr_size; i++)
cout<<arr[i]<<" ";
cout<<endl;
}
void printScoreCombination(int n, int i) {
static int arr[ARR_SIZE];
if (n == 0) {
printScore(arr, i);
}
else if(n > 0) {
int k;
for (k = 1; k <= MAX_POINT; k++){
arr[i]= k;
printScoreCombination(n-k, i+1);
}
}
}
int main() {
int n = 4;
cout<<"Different compositions formed by 1, 2 and 3 of "<<n<<" are\n";
printScoreCombination(n, 0);
return 0;
}코드 설명
- printScore(): 배열에 저장된 현재까지의 점수 조합을 화면에 출력하는 보조 함수입니다.
- printScoreCombination(n, i): 핵심 재귀 함수입니다. 매개변수 n은 남아 있는 점수, i는 배열에 저장된 현재 조합의 길이를 나타냅니다.
- 정적(static) 배열 arr은 재귀 호출 전체에서 공유되며, 각 단계에서 선택한 점수를 차례대로 저장합니다.
- n이 0이면 하나의 완성된 조합이 만들어진 것이므로 printScore()를 호출해 출력하고, n이 양수이면 1부터 MAX_POINT(3)까지의 값을 배열에 넣으며 재귀 호출을 계속합니다.
실행 결과
Different compositions formed by 1, 2 and 3 of 4 are 1 1 1 1 1 1 2 1 2 1 1 3 2 1 1 2 2 3 1
정리
이 알고리즘은 시간 복잡도가 대략 O(3^n)으로, n이 커지면 조합의 수가 기하급수적으로 늘어납니다. 따라서 작은 n에 적합하며, 순서를 구분하지 않는 조합만 필요하다면 시작 점수를 이전 점수 이상으로 제한하는 방식으로 최적화할 수 있습니다. 재귀와 백트래킹 개념을 연습하기에 좋은 대표적인 예제이므로, 직접 코드를 변형해 보면서 동작 원리를 익혀보시기 바랍니다.