백트래킹의 기본

15650번: N과 M (2)

위 문제는 백트래킹의 기본이 되는 문제이다.

백준에서 문제를 풀다보면 $size$가 $N$인 배열에서 중복 없이 $M$개를 골라야 하는 상황이 종종 온다.

여기서 $M=1,2,3$ 정도라면 구현에 부담이 없다.

$M=3$일 때,

#include <cstdio>
using namespace std;

int main() {
    int arr[n];
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < i; j++) {
            for (int k = 0; k < j; k++) {
                printf("%d %d %d\n", arr[i], arr[j], arr[k]);
            }
        }
    }
}

바로 이렇게 3중 for문으로 구현하면 $O({}_n{\mathrm{C}}_3)$으로 구현이 가능하다.

그러나 $M=10$이라면? 10중 for문을 쓸 수는 없을 것이다.

이 문제을 해결하기 위한 기본문제가 저 15650번 문제이다.

---

아래는 이 문제의 소스코드이다.

<소스 코드>

#include <cstdio>
#include <vector>
using namespace std;

void pick (int n, vector<int>& picked, int topick) {
    if (topick == 0) {
        for (int i = 0; i < picked.size(); i++) {
            printf("%d ", picked[i]);
        } printf("\n");
        return;
    }
    int smallest = picked.empty() ? 1 : picked.back()+1;
    for (int i = smallest; i < n+1; i++) {
        picked.push_back(i);
        pick(n, picked, topick-1);
        picked.pop_back();
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);
    vector<int> picked;

    pick(n, picked, m);
}

<코드 설명>

$picked$ : n개의 정수 중 고른 정수를 넣는 공간, m개가 채워지면 출력한다.

$smallest$ : 가장 중요한 값이라고 할 수 있다. 중복되지 않게, 값을 오름차순으로 고르기 위해 설정한 변수이다.