15663번

15663번 - N과M (9)

N과 M 시리즈는 같은 문제인 듯 달라서 헷갈린다.

N과 M (10)을 풀고 (9)를 풀었다. 처음에는 (9) 번에서 막혔었다..

아이디어는 같은 depth 에서 같은 숫자를 사용하면 안된다는 것! 그래서 check 배열을 만들어서 1~10000까지 숫자를 사용했는지를 체크.

그리고 used 배열을 통해서 특정 인덱스를 사용했는지 안했는지를 체크했다.

<정답 코드>

#include<iostream>
#include<algorithm>
 
using namespace std;
int num[8];
int used[8];
int op[8];
int n, k;
void go(int depth,int before)
{
    if (depth == k)
    {
        for (int i = 0; i < k; i++)
            cout << op[i] << " ";
        cout << endl;
        return;
    }
 
    int check[10001] = { 0, };
    for (int i = 0; i < n; i++)
    {
        if (!check[num[i]] && !used[i])
        {
            used[i] = true;
            check[num[i]] = 1;
            op[depth] = num[i];
            go(depth + 1, i);
            used[i] = false;
        }
    }
}
int main()
{
    cin >> n >> k;
    for (int i = 0; i < n; i++)
        cin >> num[i];
    
    sort(num, num + n);
 
    go(0,-1);
 
    return 0;
}