[백준/C] 15664 - N과 M (10)

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

구현 과정

이번엔 비내림차순 수열을 출력해야 된단다. 여태까지 푼 문제들에서 비내림차순이 나오면 bt 함수한테 start 파라미터까지 주는 방법으로 해결했었기 때문에 똑같이 해봤다. 그리고 15663번과 마찬가지로 중복을 방지하려면 bt 내에서 before 변수도 이용해야 한다!

void bt(int n, int m, int depth, int *sequence, int *nums, int *used, int start) {
    if (depth == m) {
        for (int i = 0; i < m; i++)
            printf("%d ", sequence[i]);
        printf("\n");
    }

    int before = 0;
    for (int i = start; 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, i);
            used[i] = 0;
        }
    }
}

문제점

코드 다 짰고 실행도 정상적으로 되는데 제출하니까 자꾸 'InvalidNextSize free(): invalid next size' 라는 런타임 오류가 떴다.

해결 방법

free()를 모두 주석처리하니까 맞다고 뜨긴 했는데... 이게 왜 오류가 뜨지??? 분명히 메모리 할당도 잘 했고 해제도 잘 했는데? 이유 찾으면 수정해야겠다

전체 코드

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

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

void bt(int n, int m, int depth, int *sequence, int *nums, int *used, int start) {
    if (depth == m) {
        for (int i = 0; i < m; i++)
            printf("%d ", sequence[i]);
        printf("\n");
    }

    int before = 0;
    for (int i = start; 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, i);
            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, 0);
    free(sequence);
    free(used);
    free(nums);
    return 0;
}