[백준/C] 15666 - N과 M (12)

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

구현 과정

같은 수를 여러 번 골라도 되지만, 비내림차순 수열이어야 되기 때문에 15665번 코드에다가 start 변수까지 이용하면 된다.

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

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

전체 코드

#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 start) {
    if (depth == m) {
        for (int i = 0; i < m; i++)
            printf("%d ", sequence[i]);
        printf("\n");
        return;
    }

    int before = 0;  
    for (int i = start; i < n; i++) {
        if (before != nums[i]) {
            sequence[depth] = nums[i];  
            before = 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;
}

N과 M 시리즈가 드디어 끝났다!! 재귀는 아직도 쉽지 않지만 그래도 그림 그려가면서 함수의 작동 과정에 대해서 알아보니 조금 이해가 되는 것 같았다.