[C언어 백준 풀이] N과 M (5)(8)(9)(12) 시리즈 문제들 (재귀함수 배열 재사용 등)

이 포스트에서는 프로그래밍 문제 사이트 백준 Online Judge의 시리즈 문제들인 N과 M 문제들 중 N과 M (5), (8), (9), (12)에 대한 풀이 코드와 해설을 다루고 있습니다.

 

이번 포스트에서는 Solved.ac의 Class 4 난이도에 해당하는 기본 문제들인 N과 M 시리즈들 중에서도 중 난이도의 문제들을 해결해보도록 하겠습니다. (Silver 난이도)

 

N과 M 시리즈는 N개의 정수들 중에서 M개의 정수들을 특정 규칙에 따라 가능한 모든 조합을 출력하는 문제로, 재귀함수 및 백트래킹을 연습하기 위한 문제입니다.

 

따라서 전체 구조 자체는 일정하지만, 문제의 규칙에 따라서 함수의 구조나 조건문이 달라지므로 설계 부분에서 주의를 요하는 문제들입니다.

 

 

15654번 : N과 M (5)

 

N개의 정수가 주어지고 그들 중 M개를 출력하는데, 중복 수열을 여러 번 출력하는 것은 불가능하며 반드시 수열을 오름차순으로 출력해야하는 조건이 붙은 문제입니다.

 

재귀함수와 배열의 활용을 이용하여 해결해보도록 하겠습니다.

 

#include <stdio.h>

int arr[10], check[10] = {0, }, print_arr[10], n, m, temp;

void recursion(int count) {
    if(!count) {
        for(int i=0; i<m; i++) printf("%d ", print_arr[i]);
        printf("\n");
        return;
    }
    for(int i=0; i<n; i++) {
        if(!check[i]) {
            check[i] = 1;
            print_arr[m-count] = arr[i];
            recursion(count-1);
            check[i] = 0;
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);
    for(int i=0; i<n; i++)
        for(int j=i+1; j<n; j++)
            if(arr[i] > arr[j]) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
    recursion(m);
}

 

우선 정수들을 출력하는 것은 오름차순으로 수행해야 하지만 입력은 무작위로 입력이 될 수 있기 때문에, 이를 정렬해주는 과정을 거쳐야 합니다.

C++의 algorithm.h를 사용해도 되지만 O(N^2) 정렬 알고리즘을 사용해도 무방할 정도로 데이터의 수가 많지 않기 때문에 직접 정렬을 수행하였습니다.

이후 전역 변수로 선언한 배열을 활용하는데, 중요한 점은 각 수행되는 재귀함수에서 배열이 어디까지 영향을 미치는지 고려하는 것이 중요합니다.

예를 들어 check 배열의 경우 for문을 돌리면서 가능한 숫자들을 한 개씩 대입해보며 재귀 과정을 거치는데, 하나의 재귀함수가 종료되면 다시 check 값을 0으로 돌려주어서 다른 번호가 사용 가능하게끔 만들어두어야 합니다.

그리고 번호를 뽑는 족족 출력하는 것이 아니라, print_arr와 같이 출력할 번호들을 저장하는 배열을 따로 선언하여 마지막에 한꺼번에 출력해주도록 해야 합니다.

그렇지 않으면 여러 개의 재귀 함수가 비순차적으로 실행이 되면서 한 줄씩 출력이 되지 않습니다.

 

 

15657번 : N과 M (8)

 

이 문제는 역시 N개의 수가 주어지고 M개의 수를 출력하는 문제이지만, 중복 수열을 여러 번 출력하면 안 되며 사전순으로 증가하도록 수를 출력해주어야 합니다.

한 가지 조건만 제외하고 위의 문제와 형태가 아예 비슷하므로, 조건문 부분만 수정해주면 쉽게 해결이 가능할 것으로 보입니다.

 

#include <stdio.h>

int arr[10], check[10] = {0, }, print_arr[10], n, m, temp;

void recursion(int count, int index) {
    if(!count) {
        for(int i=0; i<m; i++) printf("%d ", print_arr[i]);
        printf("\n");
        return;
    }
    for(int i=index; i<n; i++) {
        print_arr[m-count] = arr[i];
        recursion(count-1, i);
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);
    for(int i=0; i<n; i++)
        for(int j=i+1; j<n; j++)
            if(arr[i] > arr[j]) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
    recursion(m, 0);
}

 

저의 경우에는 recursion이라는 재귀함수에서 count를 제외하고 index라는 변수 하나를 더 선언하여 사용하였습니다.

index라는 변수는 정렬이 끝난 배열에 대해 마지막으로 선택한 번호의 index를 저장하는 용도로 사용하였습니다.

그렇기 때문에 이미 오름차순으로 정렬이 끝난 상태에서, 마지막으로 뽑은 번호 이후로만 선택을 해주는 과정이 아주 쉽게 구현될 수 있습니다.

 

 

15663번 : N과 M (9)

 

이 문제는 조금 헷갈릴 수 있는데, 입력 자체에서 수의 중복이 반영됩니다.

그렇다고 해서 출력 과정에서 중복된 수를 무제한으로 사용가능한 것이 아니라, 입력된 횟수만큼만 중복 출력이 가능하기 때문에 몇 번 카운트 되었는지까지 고려해야합니다.

 

#include <stdio.h>
int arr[10], check[10] = {0, }, print_arr[10], n, m, temp;

void recursion(int count) {
    int prev_num = 0;
    if(!count) {
        for(int i=0; i<m; i++) printf("%d ", print_arr[i]);
        printf("\n");
        return;
    }
    for(int i=0; i<n; i++) {
        if(!check[i] && prev_num != arr[i]) {
            prev_num = arr[i];
            print_arr[m-count] = arr[i];
            check[i] = 1;
            recursion(count-1);
            check[i] = 0;
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);
    for(int i=0; i<n; i++)
        for(int j=i+1; j<n; j++)
            if(arr[i] > arr[j]) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
    recursion(m);
}

 

사실 이 문제는 아주 간단하게 해결 가능한데, 바로 재귀 함수 내에서만 사용되는 변수 하나를 선언해서, 이전에 선택한 번호가 다시 선택되지 않도록 설정하는 것입니다.

예를 들어 1 2 3 3이 입력되면, 앞의 3가 먼저 선택되거나 뒤의 3이 먼저 선택되어서 1 2 3 3라는 출력이 2회 나오게 되는데, 1 2 3까지 선택한 이후 1 2 뒤에 올 숫자가 3이 다시 오지 못하게 막아버리면 중복 카운팅이 되는 것을 막을 수 있습니다.

이러한 예시 말고도 조합을 복잡하게 해서 생각해보아도 마찬기지로 해결이 됨을 알 수 있습니다.

이는 위의 코드에서는 prev_num이라는 변수에 해당하며, 전역 변수로 초기화하거나 전역 변수로 선언하고 지역 변수로 초기화해도 코드가 작동하지 않습니다.

그 이유는 재귀 함수 내에서 돌아가는 각각의 루프에 대해서 이전에 선택한 자연수를 저장해야하기 때문에, 전역 변수로 선언을 하게 되면 이 값들이 제대로 분리가 되지 않기 때문입니다.

 

 

15666번 : N과 M (12)

 

마지막으로 풀 문제는 N과 M (12)이고, 이 문제 역시 위의 문제와 조건이 비슷하지만 수들을 오름차순으로 출력하는 조건이 붙어있습니다.

이에 대한 조건은 상위에 있는 문제들에서 이미 다루었으므로 조건들을 합쳐서 코드로 작성해보겠습니다.

 

#include <stdio.h>
int arr[10], check[10] = {0, }, print_arr[10], n, m, temp;

void recursion(int count, int index) {
    int prev_num = 0;
    if(!count) {
        for(int i=0; i<m; i++) printf("%d ", print_arr[i]);
        printf("\n");
        return;
    }
    for(int i=index; i<n; i++) {
        if(arr[i] != prev_num) {
            prev_num = arr[i];
            print_arr[m-count] = arr[i];
            recursion(count-1, i);
        }
    }
}

int main() {
    scanf("%d %d", &n, &m);
    for(int i=0; i<n; i++) scanf("%d", &arr[i]);
    for(int i=0; i<n; i++)
        for(int j=i+1; j<n; j++)
            if(arr[i] > arr[j]) {
                temp = arr[i];
                arr[i] = arr[j];
                arr[j] = temp;
            }
    recursion(m, 0);
}

 

위의 문제에서 해결했던 코드에, index라는 추가 변수를 하나 더 이용하여 해결하는 방식을 이용하였습니다.

코드의 원리는 위에서 설명한 것과 마찬가지이므로 생략하도록 하겠으며, 코드에 대한 더 자세한 이해가 필요하신 분은 위의 풀이 코드를 보고 참고해주시면 될 것 같습니다.