[백준 15664] N과 M (9) (C++)

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

 

백트래킹

N과 M (5)와 비슷하게 N개의 자연수 중에 M개를 뽑아 만들 수 있는 수열을 모두 사전순으로 출력하는 문제인데

차이점은 N개의 자연수가 중복가능임

그래도 N개의 숫자 중에 M개를 뽑아야 하는 것을 변함이 없어서

그냥 중복된 숫자가 있는 숫자 카드가 N개 있고, 그 중 M개를 뽑아서 나열한 수열을 중복되지 않게, 사전순으로 출력하믄댐!

 

접근방법

N과 M(5) 코드에서 수열을 담고 있는 배열을 vector가 아닌 set으로 바꿔주면 됨~

set<vector<int>, less<vector<int>>> 이렇게 선언하면 사전순으로 수열이 정렬되어서 set에 들어감

 

오답노트

set에서 vector 정렬 안될 줄 알고 string으로 넣었다가 9, 10 이런 경우 문자열대로 사전순 정렬하면 10, 9 이렇게 나와서 틀림

set에서 벡터 그냥 정렬되니까 그냥 쓰면 될듯

 

소스코드

#include <iostream>
#include <vector>
#include <set>
#include <algorithm>
using namespace std;

vector<int> num;
set<vector<int>, less<vector<int>>> result;

void recursive(int n, int m, vector<int> arr, vector<bool> visit){
    int size = arr.size();
    if(size == m){
        result.insert(arr);
    } else {
        for(int i = 0; i < num.size(); i++){
            if(!visit[i]){
                vector<int> _arr = arr;
                _arr.push_back(num[i]);
                vector<bool> _visit = visit;
                _visit[i] = true;
                recursive(n, m, _arr, _visit);
            }
        }
    }
}

int main(){
    
    int N, M;
    cin >> N >> M;
        
    for(int i = 0; i < N; i++){
        int n;
        cin >> n;
        num.push_back(n);
    }
    
    sort(num.begin(), num.end());

    vector<int> arr;
    vector<bool> visit(N,false);
    recursive(N, M, arr, visit);

    for(const auto& s: result) {
        for(int n: s)
            cout << n << " ";
        cout << "\n";
    }
    
    return 0;
}