[백준 - 15665] N과 M (11)

1. 문제

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

15665번: N과 M (11)

2. 풀이과정

 1. N개의 자연수 중에서 M개를 고른 수열

 2. 같은 수를 여러 번 골라도 된다.

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

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

 

위의 네 가지 조건을 만족해야한다.

 

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

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

[코드설명]

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

3. 코드

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

using namespace std;
int n, m;
vector<int> arr;

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]]) {
            same_level_visited[arr[i]] = true;
            v.push_back(arr[i]);
            dfs(v, depth+1);
            v.pop_back();
        }
    }
}

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;
}