백준 15666번 : N과 M(12)

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

15666번: N과 M (12)

Code:

#include <stdio.h>
#include <stdlib.h>
 
int numbers[8] = { 0, };
int sequence[8] = { 0, };
 
void printSequence(int n, int m, int count, int start) {
    if (count == m) {
        for (int i = 0; i < m; i++) {
            printf("%d ", sequence[i]);
        }
        printf("\n");
        return;
    }
 
    int prev = -1;
    for (int i = start; i < n; i++) {
        if (prev != numbers[i]) { 
            sequence[count] = numbers[i];
            printSequence(n, m, count + 1, i);
            prev = numbers[i];
        }
    }
}
 
int compare(const void* a, const void* b) {
    return (*(int*)a - *(int*)b);
}
 
int main() {
    int n, m;
 
    scanf("%d %d", &n, &m);
 
    for (int i = 0; i < n; i++) {
        scanf("%d", &numbers[i]);
    }
 
    qsort(numbers, n, sizeof(int), compare);
 
    printSequence(n, m, 0, 0);
 
    return 0;
}

문제풀이:

1. 문제 설명

주어진 N개의 자연수 중에서 M개를 골라서 만들 수 있는 모든 수열을 비내림차순으로 출력하는 문제입니다.

2. 코드 설명

주어진 코드는 재귀 함수를 활용하여 N개의 자연수 중에서 M개의 수열을 생성하고, 오름차순으로 출력하는 과정을 수행합니다.

1. 주어진 자연수의 개수 N과 선택할 숫자의 개수 M을 입력받습니다.
2. N개의 자연수를 입력받아 numbers 배열에 저장합니다.
3. numbers 배열을 오름차순으로 정렬합니다.
4. printSequence 함수를 호출하여 수열을 생성하고 출력합니다. printSequence 함수는 다음과 같이 구현됩니다.
   • n: 전체 숫자의 개수, m: 선택할 숫자의 개수, count: 현재까지 선택한 숫자의 개수, start: 숫자 선택을 시작할 인덱스
   • count가 m과 같아지면, 숫자를 m개 선택한 경우이므로 현재까지 선택한 수열을 출력합니다.
   • 중복된 숫자를 제외하기 위해 이전에 선택한 숫자(prev)와 현재 선택한 숫자가 다를 때만 재귀적으로 다음 숫자를 선택하도록 합니다.
   • 숫자를 선택할 때마다 count를 증가시키고, 선택한 숫자를 sequence 배열에 저장합니다.
   • 재귀 호출을 통해 다음 숫자를 선택하도록 합니다.
5. 결과적으로, 주어진 N개의 자연수 중에서 M개를 선택하여 만들 수 있는 모든 오름차순 수열을 출력합니다.