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

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

구현 과정

이번에는 같은 수를 여러 번 고르면 안되며, 오름차순이 아니어도 된다.

중복 방지를 위해 used 배열을 선언하고 bt에 전달해준다. scanf하면서 0으로 초기화하는 방법보다 더 간단한, calloc으로 한번에 0으로 초기화하는 방법을 사용했다.

bt의 for문 내에서도 if (!used\[i]) 인 경우에 대해서만 나머지 과정을 실행한다.

문제점

처음에 bt 함수를 아래와 같이 구성하고,

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

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

main 내에서 bt(n, m, 0, sequence, nums, used, 0);로 호출했더니 아래처럼 start 값을 어떻게 바꿔도 계---속 [1,7], [1, 9], [1, 9] 이렇게 중복된 수열이 출력되는 오류가 생겼다. 그리고 중간에 [7, 1], [9, 1] 처럼 오름차순이 아닌 수열이 아예 출력되지 않았다.

해결 방법

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

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

• start 파라미터를 없앰
• bt 안에서 before 변수를 이용해 이전에 사용한 숫자를 저장해놓고, before에 저장된 값이 nums[i]가 아닌 경우에만 for문의 내용을 실행하게끔 if (!used[i] && before != nums[i]) 해줬다. 이를 통해 '같은 위치에서' 같은 숫자가 사용되는 것을 피할 수 있다.

전체 코드

#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;
    }

    int before = 0;
    for (int i = 0; i < n; i++) {
        if (!used[i] && before != nums[i]) {
            before = nums[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 *sequence = (int *)malloc(sizeof(int) * m);
    int *used = (int *)calloc(n, sizeof(int));
    int *nums = (int *)malloc(sizeof(int) * n);
    for (int i = 0; i < n; i++)
        scanf("%d", &nums[i]);

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

    bt(n, m, 0, sequence, nums, used);
    free(sequence);
    free(used);
    free(nums);
    return 0;
}