[C++] Boj 15663 N과 M (9)

문제 링크

15663 N과 M (9)

---

접근

N개의 수 중 M개의 수를 뽑아 수열을 만든다. 이때, 중복되는 수열은 없어야 하며, 사전순으로 출력해야 한다.

예를 들어, 4개의 수(1, 7, 9(A), 9(B)) 중 2개를 뽑아 만들 수 있는 수열은 다음과 같다.

1 7
1 9
7 1
7 9
9 1
9 7
9 9

 

(1, 7), (7, 1)은 되지만 (1, 9(A)), (1, 9(B))는 안 된다. 즉 사전순으로 중복되면 안 된다.

 

기존 백트래킹 방식에서 조금 응용하여 풀었다. 배열은 정렬되어 있다고 가정한다.

 

N개의 수(1, 7, ... ,9(A), 9(B)) 중 M개를 뽑아 만들 수 있는 수열을 만든다고 가정해 보자.

 

기존 백트래킹 방식에서는 k번째 수를 뽑은 다음, k+1번째 수를 뽑기 위해 재귀 함수를 실행한다. 

이때, k번째에서 1, k + 1번째에서 9(A)를 뽑았다고 가정하면, 9(A)와 9(B)는 중복되지만 각각 입력이 따로 들어온 다른 수이므로 isUsed 배열로는 중복 확인이 불가능하다. 이로 발생하는 문제는 (1, 9(A)), (1, 9(B))가 있다.

따라서, k번째의 depth에서 임시 변수를 만들어 9(A)를 저장한다. 자세히 말하면, (1, 9(A))를 뽑은 후 마지막으로 뽑은 숫자인 9(A)를 임시 변수에 저장한다.

백트래킹으로 (1, 9(A), ...)에서 나올 수 있는 모든 경우의 수를 찾아 k + 2번째, ..., M번째 수까지 다 뽑은 다음 다시 (1, ) (depth = k)까지 뽑았던 경우로 돌아오게 된다.

이때, depth = k의 임시 변수에 9(A)가 저장되어 있으므로, k + 1번째로 뽑을 수는 "9"를 피하면 사전순으로 중복되는 숫자를 피할 수 있다.

---

코드

#include <iostream>
#include <algorithm>
#include <unordered_set>
using namespace std;

// N개 중에서, M개 뽑음
int N, M;

// n번째로 뽑은 수를 저장
int picked[10];

// 숫자 모음
int numbers[10];

// k번째 수를 중복으로 뽑았는지 확인
bool isUsed[10];

// k 번째로 저장할 수를 탐색 
void Solve(int k)
{
    if (k == M)
    {
        for (int i = 0; i < M; i++)
            cout << picked[i] << ' ';
        cout << '\n';

        return;
    }

    // 현재 depth에서 마지막으로 뽑은 숫자 저장
    int tmp = 0;
    for (int i = 0; i < N; i++)
    {
        // 같은 인덱스인 수를 중복해서 뽑았거나,
        // 같은 수가 여러개 있을 경우 생기는 중복 수열을 피한다.
        if (isUsed[i] || tmp == numbers[i]) continue;
        isUsed[i] = 1;
        picked[k] = numbers[i];
        tmp = picked[k];
        Solve(k + 1);
        isUsed[i] = 0;
    }
}

int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> N >> M;
    for (int i = 0; i < N; i++)
    {
        cin >> numbers[i];
    }
   
    // 사전순으로 찾기 위해 배열을 정렬
    sort(numbers, numbers + N);

    Solve(0);

    return 0;
}