백준 15664번 : N과 M (10) (C 언어)

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

15664번: N과 M (10)

Code:

#include <stdio.h>
#include <stdlib.h>
 
int numbers[8] = { 0, };
int result[8] = { 0. };
int check[8] = { 0, };
 
 
int compare(const void* a, const void* b) {
    if (*(int*)a > *(int*)b) return 1;
    else  if (*(int*)a < *(int*)b) return -1;
    else return 0;
}
 
void sequence(int n, int m, int count, int cnt)
{
    if (count == m)
    {
        int flag = 0;
        for (int i = 0; i < m-1; i++)
        {
            if (result[i] > result[i + 1])
            {
                flag = 1;
                break;
            }
        }
        if (flag == 0)
        {
            for (int i = 0; i < m; i++)
            {
                printf("%d ", result[i]);
            }
            printf("\n");
        }
    }
    int tmp = -1;
    for (int i = cnt; i < n; i++)
    {
        if (check[i] == 0&&numbers[i]!=tmp)
        {
            check[i] = 1;
            result[count] = numbers[i];
            tmp = result[count];
            sequence(n, m, count + 1, cnt + 1);
            check[i] = 0;
        }
    }
}
 
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);
 
    sequence(n, m, 0 ,0);
 
    return 0;
}

문제 설명: 주어진 N개의 자연수 중에서 M개를 선택하여 비내림차순인 수열을 모두 구하는 문제입니다. 비내림차순 수열이란 각 원소가 이전 원소보다 크거나 같은 순서를 말합니다. 문제에서는 중복되는 수열을 여러 번 출력하면 안되며, 수열은 사전 순으로 증가하는 순서로 출력해야 합니다.

코드 설명:

1. int numbers[8], int result[8], int check[8]: 각각 입력받은 숫자 배열, 결과를 저장할 배열, 사용한 숫자인지 체크하는 배열을 선언합니다. 배열 크기는 문제에서 최대 크기인 8로 지정합니다.
2. int compare(const void* a, const void* b): qsort 함수에서 사용할 비교 함수입니다. 오름차순으로 정렬하기 위해 비교 함수를 작성합니다.
3. void sequence(int n, int m, int count, int cnt): 수열을 생성하는 재귀 함수입니다. 비내림차순인 수열을 찾고 출력합니다.
4. qsort(numbers, n, sizeof(int), compare): 입력받은 숫자 배열을 비내림차순으로 정렬합니다.
5. sequence(n, m, 0, 0): 수열을 생성하는 함수를 호출하여 문제의 조건을 만족하는 수열을 출력합니다.