[백준/C] 15656 - N과 M (7)

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

구현 과정

문제의 조건을 살펴보면

입력받은 n개의 수 중에서 m개의 숫자를 골라 수열 만들기
같은 수를 여러 번 선택 가능
오름차순이 아니어도 됨

이라는 조건이 있다. 따라서 bt 함수에는 n, m, depth, *sequence, *nums만 전달해주면 된다.

처음 코드를 실행했더니 [9, 9], [9, 8] ... 이렇게 반대 순서로 출력이 돼서 뭐가 문제지 했는데..! 이 문제에서도 사전 순 증가하는 순서로 출력해야 되기 때문에 nums에 숫자를 입력받고 나서 정렬을 해줘야 하는 것이었다. 따라서 qsort를 추가해주었다.

전체 코드

#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) {
    if (depth == m) {
        printSequence(m, sequence);
        return;
    }

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

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

    int *sequence = (int *)malloc(sizeof(int) * m);
    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);
    free(sequence);
    free(nums);
    return 0;
}