[백준/C] 15655 - N과 M (6)

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

구현 과정

15654번이랑 굉장히 비슷하지만! 오름차순인 수열만 출력해야 된다는 조건이 추가되었다. 따라서 bt 함수의 파라미터로 start를 추가해서 이전 요소보다 큰 요소만 선택하게끔 만들어줬다.

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, i);
            used[i] = 0;
        }
    }
}

bt 함수 내의 for문을 i = start 부터 시작하게끔 했고, 다음 bt의 호출 시 start 값으로 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, 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, i);
            used[i] = 0;
        }
    }
}

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

    int nums[n];
    int used[n];
    for (int i = 0; i < n; i++) {
        scanf("%d", &nums[i]);
        used[i] = 0;
    }

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

    int sequence[m];
    bt(n, m, 0, sequence, nums, used, 0);
    return 0;
}

N과 M 문제들 이 짤 같다...