백준 15654 N과 M (5) | 조합 | C++

 

 

이번 포스팅은 백준 15654번 N과 M (5)입니다.

아래 url를 클릭하시면 백준 사이트에서 문제를 볼 수 있습니다.

www.acmicpc.net/problem/15654

15654번: N과 M (5)

 

 

 

기본 알고리즘

조합을 재귀함수로 구현

 

15650번과 정렬이 되어있지 않은 입력 값들이 들어온다는 점만 제외하면 동일한 문제

15650번 풀이 참고 - scarlettb.tistory.com/125

백준 15650 N과 M (2) | 조합 | C++

 

 

 

전체 코드

 

//백준15654 N과 M (5)                                                        
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
const int MAX = 8;
int N, M;
vector<int> list;
bool selected[MAX];
vector<int> ans;
 
void print() {
    for (int i = 0; i < ans.size(); i++) {
        cout << ans[i] << " ";
    }
    cout << "\n";
}
 
void DFS(int cnt) {
    if (cnt == M) {
        print();
        return;
    }
    for (int i = 0; i < N; i++) {
        if (selected[i]) continue;
        selected[i] = true;
        ans.push_back(list[i]);
        DFS(cnt + 1);
        ans.pop_back();
        selected[i] = false;
    }
}
 
int main() {
    cin >> N >> M;
    for (int i = 0; i < N; i++) {
        int n;
        cin >> n;
        list.push_back(n);
    }
 
    sort(list.begin(), list.end());
 
    DFS(0);
 
    return 0;
}