백준 15666번, N과 M (12)

백준 15663번 c++ 문제풀이

문제:

백준 15666

풀이:

1. dfs를 이용하기 위해 재귀함수를 만든다.
2. 중복으로 수를 고를 수 있으나 똑같은 수열을 여러개 만들 수 없다.
3. 따라서 m개의 길이의 수열을 만든다고 했을 때, n번 째 숫자를 고를 때 똑같은 수를 두번 고를 수 없다.
4. 주어진 숫자 중, 중복된 숫자가 있다면 제거해주면 된다.

코드:

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

using namespace std;

int arr[9];

void dfs(vector<int> v, int m, int n, int count, int before){
    if(count == m){ // 현재 수열이 완료가 되었다면 출력
        for(int i=0;i<m;i++){
            cout << arr[i] <<" ";
        }
        cout << "\n";
    }
    else{
        for(int i=0;i<v.size();i++){
            if(v[i] >= before && v[i-1] != v[i]){ //만든 수열에서 수가 겹치는 것은 되지만, 만든 수열 끼리는 겹치면 안됨
                arr[count] = v[i];
                count++;
                dfs(v, m, n, count, v[i]);
                count--;
            }
            
        }
    }
}

int main(){

    int m, n;

    vector<int> v;

    cin >> n >> m;

    for(int i=0;i<n;i++){
        int input;

        cin >> input;

        v.push_back(input);
    }
    sort(v.begin(), v.end()); //정렬시켜준다.

    dfs(v, m, n, 0, 0);

}

감사합니다.