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

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

문제 설명

입력 및 출력 설명과 예제 입력 / 출력

 

 이 N과 M 문제 시리즈들을 연속으로 풀어보고 있는데, 새삼 next_permutation 함수에 너무 익숙해져 있던 스스로를 발견했다.. 간단한 조합과 순열 알고리즘 들을 이번 기회에 다시 돌아보게 되는 계기가 되었다. 

 

 우선 이 문제는 백트래킹 알고리즘을 사용해서 풀면 쉽다는 것을 깨달은 건 꽤나 오랜 시간이 지난 후였다. 처음부터 swap을 통해 값을 바꿔주면서 조합 비스무리하게 하면 될 것 같다는 생각은 했는데, 백트래킹까지는 생각을 못했었다. 

 

 중복 허용을 하지 않으므로 백트래킹 알고리즘을 사용해서 모든 index를 접근해보되 이미 원소로 뽑힌 index는 lock을 걸어 접근하지 못하게 하고, 나머지 접근 되지 못한 원소들이 자연스럽게 접근되도록 하는 알고리즘이 필요하다.

 

여기서 lock은 check 배열을 사용하여 1인 경우와 0인 경우로 나누어 뽑힐 수 있냐 없냐의 차이로 생각하면 된다.

 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

bool cmp(int a, int b){
    return a<b;
}

int num, howmany, n;
int lst[9];
int check[9];
int result[9];

void Permutation(int len){
    if(len==howmany){
        for(int i=0;i<howmany;i++){
            cout << result[i] << " ";
        }
        cout << '\n';
    }
    else{
        for(int i=0;i<num;i++){
            if(check[i]==0){
                result[len] = lst[i];
                check[i] = 1;
                Permutation(len+1);
                check[i] = 0;
            }
        }
    }
}

void swap(int& a, int& b){
    int temp = a;
    a = b;
    b = temp;
}

int main() {
    cin >> num >> howmany;
    for (int i=0;i<num;i++){
        cin >> lst[i];
    }
    sort(lst,lst+num);
    Permutation(0);

    return 0;
}