#15655번 N과 M(6) (C++)

문제 링크 : www.acmicpc.net/problem/15655

15655번: N과 M (6)

N과 M씨리즈 중 마지막으로 인상깊었던 문제이다.

원리를 알면 어렵지 않지만, 생각없이 풀다가 시간이 다소 소요되었다.

 

보다시피 작은 순으로 역순 출력이 불가능하고, 오로지 오름차순으로만 답이 출력되어야한다.

기존 N과 M문제랑 큰 차이는 없는데, 한 가지 중요한 점은 시작지점을 받아서 다음값으로는 시작지점보다 큰 위치에서 값을 저장해야한다는 것이다.

 

기본적으로 N과 M(5)에서 크게 벗어나지 않으므로, 구체적인 해설은 생략한다.

 

#include <iostream>
#include <algorithm>
const int MAX = 9;
using namespace std;

int arr[MAX] = {0,}, temp[MAX] = {0,}, n=0, m=0;
bool ch[MAX] = {false,};

void go(int start, int index, int cnt){
    if(cnt==0){
        for(int i=1; i<=m; i++){
            cout << temp[i] << " ";
        }
        cout << "\n";
        return;
    }
    for(int i=start; i<=n; i++){
        if(!ch[i]){
            ch[i] = true;
            temp[index] = arr[i];
            go(i+1, index+1, cnt-1);
            ch[i] = false;
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for(int i=1; i<=n; i++){
        cin >> arr[i];
    }
    sort(arr, arr+n+1);
    go(1,1,m);   
    return 0;
}