백준 15663번, N과 M(9) (C,C++)

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

15663번: N과 M (9)

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

using namespace std;

bool visited[10001];
bool visited2[10001][9];
vector<int> a;
int arr[9];
int N;
int M;

void combination(int cnt){
    if(M == cnt){
        for(int i = 0; i < M; i++){   
            cout<<a[i]<<' ';
        }
        cout<<'\n';
        return;
    }
    for(int i = 0; i < N; i++){
        if(visited[i] == true || visited2[arr[i]][cnt] == true){
            continue;
        }
        visited[i] = true;
        visited2[arr[i]][cnt] = true;
        a.push_back(arr[i]);
        combination(cnt + 1);
        visited[i] = false;
        a.pop_back();
    }
    for(int i = 0; i < N; i++){
        visited2[arr[i]][cnt] = false;
    }
}

int main(){
     ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);


    cin>> N >> M;
    for(int i = 0 ; i < N; i++){ 
        cin>>arr[i];     
    }
    sort(arr, arr + N);
    combination(0);
}

예시를 들어봅시다.

4개의 숫자가 있습니다.

{9, 7, 9, 1}

그 중에서 2가지를 뽑아서 만들 수 있는 수열은

{1, 7} {1, 9} {1, 9} {7, 1} {7, 9} {7, 9} {9, 1} {9, 7} {9, 7} {9, 9}입니다.

중복되는 수열은 출력을 하면 안되므로

{1, 7} {1, 9} {7, 1} {7, 9} {9, 1} {9, 7} {9, 9}입니다.

 

sort 함수를 이용해 {1, 7, 9, 9}로 만들어줍시다.

arr[0] = 1, arr[1] = 7, arr[2] = 9, arr[3] = 9입니다.

위 그림을 통해 설명하도록 하겠습니다.

위 그림의 직사각형은 함수가 시행된 것이라고 보면 이해하기가 쉬울 것 입니다.

이 그림에서 설명대로 따라간다면, {1, 7}을 출력할 것입니다. 

 

 

 

 

위 그림을 통해서 저희는 {1, 7}, {1, 9}을 출력하게 되는 것을 알 수 있습니다.

가운데에 있었던 직사각형으로 표현한 재귀함수는 모든 일을 다하여 함수가 종료됩니다.

이 과정을 수의 갯수만큼 반복해 주시면 되겠습니다.

 

이 문제의 키 포인트는 2차 배열을 세우고, 2차 배열의 요소에 배열로 표현된 수를 넣는 방식을 통해서 중복되게 만드는 것이다

ex) 위 그림에서 visited2[arr[2]][cnt]와 visited2[arr[3]][cnt]는 같다.