[백준 - 15663] N과 M (9) [C++]

1. 문제

https://www.acmicpc.net/problem/15663

15663번: N과 M (9)

2. 풀이과정

N개의 자연수 중에서 M개를 고른 수열을 출력하는 문제인데, 아래의 조건들을 만족해야한다.

  1. 중복되는 수열을 여러 번 출력하면 안된다.

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

 

N = 4, M = 2

N개의 수 = {9, 7, 9, 1}일 때,

1 7

1 9

7 1

7 9

9 1

9 7

9 9

가 출력되어야 한다. 

 

2번 조건을 만족하기 위해 N개의 수를 오름차순 정렬한다.

N개의 수  = {1, 7, 9, 9}

 

그림1

 

1번조건을 만족하기 위해선 그림1과 같이 같은 레벨에서 같은 수를 중복 방문하지 않아야한다.

 

[코드설명]

dfs함수는 문제의 조건을 만족하는 N개의 자연수 중에서 M개를 고른 수열을 출력해준다.

3. 코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;
int n, m;
vector<int> arr;
bool visited[8];


void dfs(vector<int>& v, int depth) {
    if(depth == m) {
        for(int i=0; i<m; i++) cout << v[i] << " ";
        cout << "\n";
        return ;
    }
    bool same_level_visited[10001] = {false};
    for(int i=0; i<n; i++) {
        if(!same_level_visited[arr[i]] && !visited[i]) {
            v.push_back(arr[i]);
            visited[i] = true;
            same_level_visited[arr[i]]=true;
            
            dfs(v, depth+1);
            
            v.pop_back();
            visited[i] = false;
            
        }
    }
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i=0; i<n; i++) {
        int tmp;
        cin >> tmp;
        arr.push_back(tmp);
    }
    sort(arr.begin(), arr.end());
    vector<int> v;
    dfs(v, 0);
    return 0;
}