2학기 7주차_알고리즘( 백준15651번 : N과 M(3) )

 

 

문제

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오.

• 1부터 N까지 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.

입력

첫째 줄에 자연수 N과 M이 주어진다. (1 ≤ M ≤ N ≤ 7)

출력

한 줄에 하나씩 문제의 조건을 만족하는 수열을 출력한다. 중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

 

 

 

📌내풀이

 

 

문제를 보자마자 지난 주차들에서 풀었던 M과 N들이 떠올랐다.

 

여러가지 구조들을 공부할 수 있는 문제들이구나 생각하면서 풀어보는데 , 아직은 내가 배울게 많은 것 같다 라고 생각하고 이런 저런 풀이 방법들을 찾아보았다. 

 

#include <stdio.h>

int N, M, arr[8];

void func(int depth) {
    if (depth == M) {
        for (int i = 0; i < M; i++)
            printf("%d ", arr[i]);
        printf("\n");
        return;
    }

    for (int i = 1; i <= N; i++) {
        arr[depth] = i;
        func(depth + 1);
    }
}

int main() {
    scanf("%d %d", &N, &M);
    func(0);
    return 0;
}

 

 

  해당 문제는 재귀함수를 이용하여 풀이할 수 있는 문제이다.

 

1. 우선 N과 M을 변수로 설정하고, 크기8에 arr를 선언, 이는 선택된 숫자를 저장하는데 사용되는 배열이다.
2. func 함수는 현재까지의 선택 상태를 나타내는 depth를 인자로 받는다.
3. depth가 M과 같아지면 반복문을 통해서 0부터 M보다 작을때까지 1씩 증가하면서 배열을 저장해준다.
4. 그렇지 않으면 1부터 N까지의 숫자를 arr[depth]에 저장하고, depth + 1에 대해 func 함수를 호출하도록한다.
5. main 함수에서는 scanf 함수를 사용하여 N과 M을 입력받은 후, func(0)을 호출하여 프로그램을 실행한다.

  이렇게 중복을 허용하여 M개를 선택하는 모든 조합을 출력하도록 하는 것이다.

 

 

 

 

 

설탕 문제보다는 살짝 까다로웠지만, 공부를 하고 나니 막상 그렇게 어려운 문제는 아닌 것 같다.

컴퓨터 알고리즘 관련 수업을 들었으니, 이런 복잡하게 느껴지는 알고리즘을 직접 그려보면서 공부하는 것도 좋은 방법일거란 생각이 들었다.

 

알고리즘 과제 끝,

 

 

[ 참고 학습 자료 ]

 

[C언어] 재귀함수란? 재귀함수 예시, 쉬운 설명 :: 안산드레아스 (tistory.com)

[C언어] 재귀함수란? 재귀함수 예시, 쉬운 설명

 

[백준] 15651번 N과 M (3) - C/C++ (easyso2z.com)

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