[백준] N과 M (12)

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

15666번: N과 M (12)

문제부터 간단하게 요약하면, 

 

중복 조합으로 숫자를 M개 뽑아서 오름차순으로 출력해야 하는 문제였습니다. 

 

<Solution>

DFS를 이용하여 구현하였습니다. 

코드는 아래와 같습니다. 

#include <iostream>
#include <algorithm>
#include <set>

using namespace std;

int N, M;
int num_array[10];
int num_array_[10];
int print_num[10];
int cur_index;

void getinput(){
    cin >> N >> M;
    int k ;
    for(int i = 0; i<N; i++){
        cin >> num_array[i];
    }
}

void dfs(int turn, int before_index){

    if(turn == M){
        // print num 
        for(int i = 0; i<M; i++){
            cout << print_num[i] << ' ';
        }
        cout << endl;
        return;

    }

    for(int i = before_index; i<cur_index; i++){
        print_num[turn] = num_array_[i];
        dfs(turn+1, i);
    }
    return;

}

void solution(){
    sort(num_array, num_array+N);
    // remove duplicate
    cur_index = 1;
    int before_val = num_array[0];
    num_array_[0] = num_array[0];
    for(int i = 1; i<N; i++){
        if(before_val == num_array[i]) continue;

        num_array_[cur_index++] = num_array[i];
        before_val = num_array[i];
    }

    dfs(0, 0);

}

int main(){
    getinput();

    solution();

    return 0;


}