[BOJ] 백준 15663 N과 M(9)

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

Approach

▶ 순열과 조합 (백준 N과 M 시리즈) 

순열과 조합 (백준 N과 M 시리즈)

 

[BOJ] 15654 N과 M(5) 문제와 달리 주어지는 Input Data가 중복이 있을 수 있다.

따라서 중복 없는 순열을 구현하면서 이미 선택한 숫자인지도 판단하여야 한다.

 

이는 정렬된 Input Data에서 지역 변수 하나로 쉽게 판단할 수 있다.

"prev" 라는 이전에 선택된 숫자를 담아서 중복 되었는지를 알 수 있다.

ex) {1, 2, 3, 3}이 있는 상태에서 네번째 "3"은 앞에 위치한 "3"이 선택되었기에 제외

 

전역 변수로 두지 못하는 것은 재귀함수로 비교할 때, 첫번째로 선택되는 숫자가

prev와 관계없이 선택되어지기 위함이다.

 

---

#include <stdio.h>
const int MAX_N = 8 + 2;
int N, M, ans[MAX_N], arr[MAX_N], trr[MAX_N];
bool visited[MAX_N];

void input()
{
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; ++i)
    {
        scanf("%d", &arr[i]);
    }
}

void mergeSort(int start, int end) {
    // 0. base condition
    if (start >= end) return;
    // 1. divide
    int mid = (start + end) / 2;
    // 2. conquer
    mergeSort(start, mid);
    mergeSort(mid + 1, end);
    // 3. merge
    int i = start, j = mid + 1, k = start;
    while (i <= mid && j <= end) {
        if (arr[i] < arr[j])
            trr[k++] = arr[i++];
        else
            trr[k++] = arr[j++];
    }
    while (i <= mid) trr[k++] = arr[i++];
    while (j <= end) trr[k++] = arr[j++];
    // 4. copy
    for (i = start; i <= end; ++i) {
        arr[i] = trr[i];
    }
}

void DFS(int depth) {
    if (depth == M) {
        for (int i = 0; i < M; ++i) {
            printf("%d ", ans[i]);
        }
        printf("\n");
        return;
    }

    // 전역 변수가 아닌 지역변수
    int prev = -1;

    for (int i = 0; i < N; ++i) {
        if (visited[i]) continue;
        if (prev == arr[i]) continue;
        
        visited[i] = true;
        prev = ans[depth] = arr[i];
        DFS(depth + 1);
        visited[i] = false;
    }
}

int main() {
    // freopen("input.txt", "r", stdin);
    input();
    mergeSort(0, N-1);
    DFS(0);
}

 

Reference

- 합병 정렬(Merge Sort) 

- 순열과 조합 (백준 N과 M 시리즈) 

- [BOJ] 15649 N과 M (1)

- [BOJ] 15654 N과 M(5)