백준 15649 : N과 M(1)

문제 링크입니다 https://www.acmicpc.net/problem/15649

15649번: N과 M (1)

자연수 N과 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 문제였습니다.

조건은 다음과 같고,

 

- 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열

 

재귀 호출을 통해 M개를 고를 때마다 수열을 출력해주는 방식으로 문제를 해결했습니다.

 

 

[소스코드]

 

#include<cstdio>
 
int n, m;
int result[10]; // 수열을 담을 배열
bool check[10]; // 중복을 없애기 위한 배열
 
void getResult(int x) {
    // 1 ~ n까지의 수 중 중복 없이 m개를 고른 수열을 출력
    if (x >= m) {
        for (int i = 0; i < m; i++) {
            printf("%d ", result[i]);
        }
        printf("\n");
    }
    else {
        for (int i = 1; i <= n; i++) {
            // 1부터 n까지의 수들 중에서 아직 고르지 않았다면
            if (!check[i]) { 
                result[x] = i;      // 배열에 넣고
                check[i] = true;    // 골랐습니다
                getResult(x + 1);   // 다음 수를 고르러 갑니다
                
                // 출력이 끝나면 모든 탐색을 보기 위해
                check[i] = false;
                result[x] = 0;
            }
        }
    }
}
 
int main(void) {
    scanf("%d%d", &n, &m);
    getResult(0);
    return 0;
}