[백준] N과 M (9)

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

15663번: N과 M (9)

문제부터 요약하면, 

N개의 숫자가 주어질 때, 조건에 알맞게 M개를 뽑아서 사전순으로 출력해야 합니다.

이 문제의 조건은 중복되는 수열이 없도록 출력해야 하는 것이 조건이였습니다.

 

<Solution>

일반적인 DFS의 로직에서 used 배열을 두어서 각 숫자마다 사용 가능 횟수를 체크해서 사용 가능한 경우에만 상태 발전이 이루어지도록 하여 구현하였습니다.

 

실제 구현은 아래와 같습니다.

#include <iostream>
#include <algorithm>

using namespace std;

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

int print_num[10];
int used[10000+10];

int cnt[10000+10];

int k;

void getinput(){
    cin >> N >> M;
    for(int i = 0; i<N; i++){
        cin >> num_array[i];
        cnt[num_array[i]]++;
    }
    // 중복제거
    sort(num_array, num_array+N);

    // first number just push

    num_array_[k] = num_array[k];
    k++;
    for(int i = 1; i<N; i++){
        if(num_array_[k-1] == num_array[i]) continue;

        num_array_[k] = num_array[i];
        k++;
    }

}

void dfs(int turn){

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

    // 상태발전
    for(int i = 0; i<k; i++){
        // 사용 더 못하는 경우 continue
        if(used[num_array_[i]] >= cnt[num_array_[i]]) continue;

        // 사용가능시 상태발전
        used[num_array_[i]]++;
        print_num[turn] = num_array_[i];
        dfs(turn+1);
        used[num_array_[i]]--;

    }

}

void solution(){

    dfs(0);


}

int main(){
    getinput();

    solution();

    return 0;


}