[백준/C언어] 15651번 - N과 M (3)

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

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

 

---

문제

15651번: N과 M (3)

---

소스 코드

#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{
        for(int i=1; i<=N; i++){
            arr[count] = i;
            search(arr, count+1, N, M);
        }
    }
}

---

문제 풀이

  주어진 조건을 만족하는 수열을 모두 출력하는 문제입니다. 앞선 문제들 15649번, 15650번 문제와 같이 재귀함수를 정의하여 백트래킹으로 해결할 수 있습니다.

  '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[count]에 범위 내 자연수 차례로 저장, 재귀
- 재귀: search(arr, count+1, N, M)