[algorithm] 백준 - N과 M(9)

이 문제는 dfs이다.

중복되는 수열을 여러번 출력하면 안되며,
수열은 중복된 수로 나열되어있을 수 있다.

이 문제는 N과 M(5)와 연관된 문제이다.

포인트는

'N과 M(5) + 재귀 시 중복된 수가 있는지 확인'

이다.

N과 M(5) 문제 또한 dfs인데, 순열과 조합이 섞인 문제이다.

즉, N개로 이루어진 자연수 중에서 M개를 고르고 나열하는 문제이다.

//백준 N과 M (5)
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

bool selected[9] = {false};
void permutationAndCombination(int target, int index, vector<int> realNumVector, vector<int> numVector){
    if(target == index){
        for(int i = 0; i < numVector.size(); i++){
            cout << numVector[i] << " ";
        }
        cout << "\n";
        return;
    }
    for(int i = 0; i < realNumVector.size(); i++){
        if(selected[i]) continue;
        selected[i] = true;
        numVector.push_back(realNumVector[i]);
        permutationAndCombination(target, index + 1, realNumVector, numVector);
        numVector.pop_back();
        selected[i] = false;
    }
}
int main(void){
    int count, target, num;
    cin >> count >> target;
    vector<int> realNumVector;
    for(int i = 0; i < count; i++){
        cin >> num;
        realNumVector.push_back(num);
    }
    sort(realNumVector.begin(), realNumVector.end());
    vector<int> numVector;
    permutationAndCombination(target, 0, realNumVector, numVector);
}

그럼 이 코드를 어떻게 변환시켜야할까?
재귀 시 중복된 수가 있는지 확인하면 된다. 즉, 재귀 하기 직전에 수를 기록해두고
이 수와 동일하지 않을 경우만 처리한다.

int beforeNum = -1;
    for(int i = 0; i < realNumberVector.size(); i++){
        if(!selected[i] && beforeNum != realNumberVector[i]){
            beforeNum = realNumberVector[i];
            selected[i] = true;
            numVector.push_back(realNumberVector[i]);
            permutation(index + 1, target, realNumberVector, numVector);
            numVector.pop_back();
            selected[i] = false;
        }
    }

 

전체적인 코드는 이렇다.

//백준 N과 M (9)
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

bool selected[9] = {false};
void permutation(int index, int target, vector<int> realNumberVector, vector<int> numVector){
    if(index == target){
        for(int i = 0; i < numVector.size(); i++){
            cout << numVector[i] << " ";
        }
        cout << "\n";
        return;
    }
    int beforeNum = -1;
    for(int i = 0; i < realNumberVector.size(); i++){
        if(!selected[i] && beforeNum != realNumberVector[i]){
            beforeNum = realNumberVector[i];
            selected[i] = true;
            numVector.push_back(realNumberVector[i]);
            permutation(index + 1, target, realNumberVector, numVector);
            numVector.pop_back();
            selected[i] = false;
        }
    }
}
int main(void){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int count, target, num;
    cin >> count >> target;
    vector<int> realNumberVector;
    for(int i = 0; i < count; i++){
        cin >> num;
        realNumberVector.push_back(num);
    }
    vector<int> numVector;
    sort(realNumberVector.begin(), realNumberVector.end());
    permutation(0, target, realNumberVector, numVector);
}

https://github.com/jeongdaeun98/algorithm/blob/master/2020/20102901.cpp

jeongdaeun98/algorithm