백준 15665번 N과 M (11) - C++ 풀이

---

 

1. 숫자를 하나씩 총 M개 뽑는다.
2. 숫자를 뽑을 때는 작은 숫자부터 뽑아본다.
3. 후보 숫자 목록에 중복이 없도록 후보 숫자들을 배열이 아닌 set으로 관리한다.

 

1. 숫자를 하나씩 총 M개 뽑는다.

 N개의 후보 숫자 중에서 총 M개 뽑으면 수열이 완성된다. M개를 다 뽑았으면 완성된 수열을 출력해주는 것을 반복한다.

 

2. 숫자를 뽑을 때는 작은 숫자부터 뽑아본다.

 수열을 사전 순으로 증가하는 순서로 완성해야 한다. 따라서 뽑을 때 더 작은 숫자를 먼저 뽑아야 한다. (0으로 시작하는 수열을 1로 시작하는 수열보다 먼저 출력해야 하므로 0부터 뽑아보는 것이다.)

 

3. 후보 숫자 목록에 중복이 없도록 후보 숫자들을 배열이 아닌 set으로 관리한다. 

  그런데 중복되는 수열을 출력하면 안된다. 중복되는 수열이 생기는 경우는 같은 후보 숫자를 다른 숫자처럼 처리하는 경우에 발생한다. 예를들어, 주어진 후보 숫자 N개가 [1, 2, 2, 2, 8]일 때 첫번째 숫자를 고르는 경우의 수는 1 or 2 or 8로 3가지 뿐이다. 여러 개의 2가 있더라도 모두 같은 2로 처리해주어야 한다. 이는 애초에 후보 숫자 목록에 중복이 없으면 간단하게 해결된다. 후보 숫자 목록에 중복이 없도록 set에 담아 관리해주는 방법을 쓸 수 있다.

 

---

#include <iostream>
#include <set>

using namespace std;

int N, M;
int sequence[7];
set<int> cands;

void printAnswer() {
    for (int i=0; i<M; i++) cout << sequence[i] << " ";
    cout << "\n";
}

void backtrack(int cnt) {
    if (cnt == M) {
        printAnswer();
        return;
    }
    
    for (auto cand: cands) {
        sequence[cnt] = cand;
        backtrack(cnt + 1);
    }
}

int main() {
    cin >> N >> M;
    for (int i=0; i<N; i++) {
        int temp; cin >> temp;
        cands.insert(temp);
    }
    
    backtrack(0);
    
    return 0;
}