[백준/C언어] 15650번 - N과 M (2)

백준 웹사이트 "15650번 - N과 M (2)" 문제풀이입니다.

언어는 C언어입니다. (제출 언어: C99)

 

---

문제

15650번: N과 M (2)

---

소스 코드

#include <stdio.h>
 
void search(int * arr, int count, int N, int M);
 
int main(void){
    int N, M;
    scanf("%d %d", &N, &M);
 
    int arr[M];
    search(arr, 0, N, M);
}
 
void search(int * arr, int count, int N, int M){
    if(count==M){
        //print arr
        for(int i=0; i<M; i++){
            printf("%d ", arr[i]);
        }
        printf("\n");
    }
    else{
        int prev = 1;
        if(count>0)
            prev = arr[count-1];
 
        for(int i=prev; i<=N; i++){
            int exists=0;
            for(int j=0; j<count; j++){
                if(arr[j]==i)
                    exists=1;
            }
            if(!exists){
                arr[count] = i;
                search(arr, count+1, N, M);
            }
        }
    }
}

---

문제 풀이

  이전 문제인 "15649번 - N과 M (1)"와 비슷하지만, 고른 수열이 오름차순이어야 한다는 조건이 추가로 있습니다. 소스 코드는 이전 문제의 것을 사용하되, 재귀 케이스를 문제에 맞게 수정합니다.

  'search' 재귀함수는 다음과 같이 정의합니다. 이전 문제의 search 함수와 '재귀 케이스'만 다릅니다.

함수: search(int * arr, int count, int N, int M)

파라미터
- arr : 출력할 수열 (재귀를 통해 값들을 채움)
- count : 재귀 반복 횟수, 또는 배열 arr에 값을 채운 횟수
- N : 채우는 자연수의 범위 (1부터 N까지 자연수 중에서 고름)
- M : 출력할 수열의 길이

Base Case (기본 케이스)
- 조건문: count == M
- 실행문: 배열 arr 출력

Recursive Case (재귀 케이스)
- 조건문: count != M (count가 M보다 작을 경우)
- 실행문: 현재까지 배열 arr의 마지막 숫자 확인, 이보다 큰 자연수 중 범위 내 자연수가 있다면 선택하여 arr에 추가, 재귀
- 재귀: search(arr, count+1, N, M)

 

  백트래킹 과정은 재귀 케이스의 실행문에서 배열 arr의 마지막 숫자보다 큰 자연수가 범위 내에 없을 때 나타납니다. 예를 들어 '4 4'가 입력되었을 때, 가장 먼저 '1 2 3 4' 가 출력됩니다. 이후, 배열 arr에 '1 2 4'를 차례로 넣은 후 다음에 올 숫자를 탐색한다면 4보다 큰 범위 내 수는 없기에 탐색이 중단됩니다. 그러면 백트래킹을 통해 다음 케이스 '1 3 ...'으로 넘어가 계속해서 탐색하게 됩니다. 물론 조건을 만족하는 경우는 더 이상 나오지 않기에, 정답으로 출력되는 것은 '1 2 3 4' 뿐입니다. 이렇듯 재귀를 이용해 모든 경우들을 탐색하고, 탐색 도중 조건에 어긋나게 되면 중단하고 전 단계로 돌아가 탐색을 이어나갑니다.

  아래는 백준 웹사이트 "15650번 - N과 M (1)" 문제풀이 링크입니다.

[백준/C언어] 15649번 - N과 M (1)