#15654번 N과 M(5) (C++)

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

15654번: N과 M (5)

N과 M씨리즈 중 가장 인상깊었던 문제이다.

원리를 알면 어렵지 않은데, 생각없이 풀었다가는 테스트 케이스에서 잠시 고민을 하는 상황이 발생할 수 있다.

 

문제풀이는 다음과 같다.

1. 오름차순으로 답이 출력되어야하니, 먼저 입력받은 배열을 정렬해준다.

 

 

2. 여기서 중요한 점은, 답은 오름차순으로 출력되어야하지만, 위의 케이스를 기준으로

9 1, 9 8 과 같은 답들이 출력 불가능이라는 뜻이 아니다. 때문에 오름차순을 만족하면서 위의 케이스를 성사시키려면 저장된 값들을 별도로 저장해주는 트릭이 필요하다. 

3. 배열을 하나 더 만들어, 순차적으로 입력된 값들을 저장해준다.

 

#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 index, int cnt){
    if(cnt==0){
        for(int i=1; i<=m; i++){ // 출력 갯수 m이 for문의 최대값임을 기억하자
            cout << arr[temp[i]] << " ";
        }
        cout << "\n";
        return;
    }
    for(int i=1; i<=n; i++){
        if(!ch[i]){
            ch[i] = true;
            temp[index] = i;
            go(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,m);   
    return 0;
}