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

백준 - 15663

---

풀이

기존에 풀이하던 방식은 단순히 중복을 허용하거나 하지 않는 방식이라 이번 문제를 풀이하기에는 적합하지 않다.

때문에, 기존에 i번째 요소를 사용했는지, 기존에 사용한 숫자와 현재 사용하고자 하는 숫자가 다른지 확인하는 방식으로 풀이했다. 

---

소스코드

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
bool check[8];
int N, M, arr[8], visited[8];
int compare(const void *a, const void *b){
    return *(int*)a - *(int*)b;
}
void BT(int depth){
    for (int i = 0, temp = 0; i < N; i++)
        if (!check[i] && temp != arr[i]){
            temp = visited[depth] = arr[i];
            check[i] = true;
			
            if (depth + 1 == M){
                for (int idx = 0; idx < M; idx++)
                    printf("%d ", visited[idx]);
                putchar(10);
            }else BT(depth + 1);
            check[i] = false;
        }
}
int main(){
    scanf("%d %d", &N, &M);
    for (int i = 0; i < N; i++)
        scanf("%d", &arr[i]);
    qsort(arr, N, sizeof(int), compare);
    BT(0);
}

---

출처

15663번: N과 M (9)