[백준 15663] N과 M (9)

문제

www.acmicpc.net/problem/15663

 

알고리즘

back tracking

 

풀이

N개의 자연수에서 M개를 고른 수열을 출력하되, 중복한 수열을 출력해서는 안됩니다.

 

재귀로 푸는 문제입니다. M개의 숫자를 고르는 것을 각 단계라고 생각해보겠습니다. 수열을 완성하기 위해서는 M개의 단계마다 수를 선택해야 합니다. 현재가 $i$번째 단계일 때, 당연하게도 이전에 고른 수를 선택해서는 안됩니다. 이를 확인하기 위해서 $used$배열을 사용했습니다. $used$배열은 다른 단계에서 선택한 수를 중복하지 않게 고르기 위함입니다.

 

다음으로 고려해야할 부분은 같은 단계에서 중복되는 선택입니다. $N$과 $M$이 각각 3, 2이고 숫자로 2 4 4 가 주어졌다고 해봅시다. 첫 번째 2와 두 번째 4를 고르고 수열을 하나 완성하게 되면 첫 번째 2와 세 번째 4를 고르게 되어있는데 이는 중복되는 수열을 만듭니다. 즉 현 단계에서 중복되는 숫자를 선택해서는 안됩니다. 이를 위해 $level used$배열을 사용했습니다.

 

코드

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

int N, M;
vector<int> pick, vt;
bool used[10005];
void solve(int m) {
    if (m == 0) {
        for (auto val : pick) {
            cout << val << ' ';
        }
        cout << '\n';
        return;
    }
    bool level_used[10005] {};
    rep(i, N) {
        if (!used[i] && !level_used[vt[i]]) {
            used[i] = true;
            level_used[vt[i]] = true;
            pick.emplace_back(vt[i]);
            solve(m - 1);
            pick.pop_back();
            used[i] = false;
        }
    }
}

int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N >> M;
    vt.resize(N);
    rep(i, N) {
        int& x = vt[i];
        cin >> x;
    }
    sort(vt.begin(), vt.end());
    solve(M);
    return 0;
}