[백준 15654] N과 M (5) C++

문제

백준 15654 N과 M (5) C++

15654번: N과 M (5)

풀이

n과 m (1)에서 출력값이 1 ~ n 이었다면 n과 m (5)는 사용자 입력을 받아 출력을 해야한다.

알고리즘이 바뀌는 건 없다. 백트래킹을 사용하여 순열을 출력하면 된다.

단 출력 시에는 1 ~ n을 출력하는 것이 아니라 사용자 입력을 받아 오름차순으로 정리한 vector를 출력한다.

소스 코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
int N, M;
vector<int> v;
vector<int> result;
bool isSelected[8];
 
void Print()
{
    for (int num : result)
    {
        cout << num << ' ';
    }
    cout << '\n';
}
 
void Select(int cnt)
{
    if (cnt == M)
    {
        Print();
        return;
    }
 
    for (int i = 0; i < N; i++)
    {
        if (isSelected[i])
            continue;
 
        isSelected[i] = true;
        result.push_back(v[i]);
        Select(cnt + 1);
        isSelected[i] = false;
        result.pop_back();
    }
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
 
    cin >> N >> M;
    
    int num;
    for (int i = 0; i < N; i++)
    {
        cin >> num;
        v.push_back(num);
    }
 
    sort(v.begin(), v.end());
    Select(0);
 
    return 0;
}