[백준/C] 15657 - N과 M (8)

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

구현 과정

15656번이랑 똑같은데 비내림차순이라는 조건이 추가되었다.

현재 숫자와 같거나 큰 숫자로 수열의 다음 수를 구성할 수 있게 하기 위해서 bt 함수의 파라미터로 start를 추가해준다. 이 값은 초기값이 0이며, for문 안에서 bt가 호출될 때는 i 값으로 넘겨준다. bt 안에서 for문을 돌 때도 i = start부터 시작해야 한다.

전체 코드

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

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

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, 0);
    free(sequence);
    free(nums);
    return 0;
}