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

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

---

이전 문제들처럼 1~m까지의 수들로 수열을 구성하는 것이 아니라, 입력받은 n 개의 수들 중 m개의 수를 골라서 수열을 만들어야 한다.

구현 과정

이전 문제들에서는 for문으로 i를 늘려가며 배열에 저장했기 때문에 자동으로 사전 순 정렬이 되었지만, 이렇게 숫자를 직접 입력받는 경우 사전순으로 정렬하고 싶다면 bt를 처음 호출하기 전에 미리 nums의 숫자들을 사전순으로 정렬해야 한다. 이를 위해 qsort 함수를 이용했다.

#include <stdlib.h>

int compare(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

qsort(nums, n, sizeof(int), compare); // main() 내에서

이 문제에서는 수열에 사용할 숫자들을 직접 입력받기 때문에, 숫자를 입력받은 nums 배열도 마찬가지로 bt에 전달해주어야 한다.

같은 수를 두 번 사용할 수 없기 때문에, used\[n] 배열을 선언하고 모든 값을 0으로 초기화해 준다. 이미 사용한 숫자를 체크해야 하기 때문에 bt가 호출될 때마다 used 배열이 전달되어야 한다. bt 내에서는 !used\[i]인 경우에만 배열에 저장하는 작업을 실행한다.

배열에 저장할 때는

sequence[depth] = nums[i];

로 저장해준다는 것이 이전 문제들과의 가장 큰 차이점이다. 정렬된 배열에서 하나씩 빼서 저장해주는 것이다!

sequence 배열에 저장한 뒤에는

1. 해당 숫자를 사용한 것이므로 used\[i] = 1 해준다.
2. bt 다시 호출
3. bt가 return되어서 다시 여기로 돌아왔을 때, 숫자를 다시 사용할 수 있게 하기 위해서 used\[i] = 0 으로 다시 바꿔준다. (재귀함수 그려보면 이해 가능)

used[i] = 1;
bt(n, m, depth + 1, sequence, nums, used);
used[i] = 0;

재귀함수의 작동 과정

---

전체 코드

#include <stdio.h>
#include <stdlib.h>

int compare(const void *a, const void *b) {
    return *(int *)a - *(int *)b;
}

void printSequence(int m, int *sequence) {
    for (int i = 0; i < m; i++)
        printf("%d ", sequence[i]);
    printf("\n");
}

void bt(int n, int m, int depth, int *sequence, int *nums, int *used) {
    if (depth == m) {
        printSequence(m, sequence);
        return;
    }

    for (int i = 0; i < n; i++) {
        if (!used[i]) {
            sequence[depth] = nums[i];
            used[i] = 1;
            bt(n, m, depth + 1, sequence, nums, used);
            used[i] = 0;
        }
    }
}

int main() {
    int n, m;
    scanf("%d %d", &n, &m);

    int nums[n];
    for (int i = 0; i < n; i++)
        scanf("%d", &nums[i]);

    qsort(nums, n, sizeof(int), compare);

    int used[n];
    for (int i = 0; i < n; i++)
        used[i] = 0;

        int sequence[m];
    bt(n, m, 0, sequence, nums, used);
    return 0;
}