[백준/C++] 15664번 N과 M(10)

문제

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A ≤ A ≤ ... ≤ A ≤ A를 만족하면, 비내림차순이라고 한다.2K
  • K-1
  • 1

입력

첫째 줄에 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 8)

둘째 줄에 N개의 수가 주어진다. 입력으로 주어지는 수는 10,000보다 작거나 같은 자연수이다.

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

예제 입력 1

3 1
4 4 2

예제 출력 1

2
4

예제 입력 2

4 2
9 7 9 1

예제 출력 2

1 7
1 9
7 9
9 9

예제 입력 3

4 4
1 1 2 2

예제 출력 3

1 1 2 2

 

 

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

int n, m;
vector<int> arr;
vector<int> ans;
bool check[9] = {false, };

void dfs(int cnt) {
    if (cnt == m) {
        for (int i = 0; i < m; i++) {
            cout << ans[i] << ' ';
        }
        cout << '\n';
        return;
    }
    int before = -1;
    for (int i = 0; i < n; i++) {
        if (!check[i] && (before != arr[i])) {
            check[i] = true;
            before = arr[i];
            ans[cnt] = arr[i];
            dfs(cnt + 1);
            check[i] = false;
        }
    }
}

int main() {
    cin >> n >> m;
    arr.resize(n);
    ans.resize(n);
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }
    sort(arr.begin(), arr.end());
    dfs(0);
    return 0;
}

백트래킹 기법을 이용한 dfs 함수를 만들어 문제를 푼다

• 현재 선택된 숫자의 개수를 인자로 받고, 숫자의 개수가 m과 같다면 출력한다
• 그렇지 않다면 아직 선택하지 않은 숫자 중에서 하나를 선택하고 dfs함수를 재귀적으로 호출한다
• check 배열은 반복문을 돌며 i 번째 숫자의 선택 여부를 확인 한다