백준 15652 : N과 M(4)

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

15652번: N과 M (4)

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

조건은 다음과 같고,

 

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

- 같은 수를 여러 번 골라도 된다.

- 고른 수열은 비내림차순이어야 한다.

      → 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

 

재귀 호출을 통해 중복을 허용하고 항상 크거나 같은 수를 고를 수 있도록 하여 M개를 고를 때마다 수열을 출력해주는 방식으로 문제를 해결했습니다.

 

 

[소스코드]

 

#include<cstdio>
#include<algorithm>
using namespace std;
 
int n, m;
int result[10]; // 수열을 담을 배열
 
// 1 ~ n까지의 수 중 중복을 허용하여 m개를 골라 출력해주는 함수
// 단, 비내림차순의 수열을 출력합니다
void getResult(int count, int start) {
 
    // 1 ~ n까지의 수 중 m개를 고른 수열을 출력
    if (count == m) {
        for (int i = 0; i < m; i++)
            printf("%d ", result[i]);
        printf("\n");
        return;
    }
    // 1부터 n까지의 수 중에서 선택합니다
    for (int i = start; i <= n; i++) {
        result[count] = i;       // 배열에 넣습니다
 
        // 다음 수를 고르러 가는데 start에 해당하는 인자에는
        // i를 넣어주어 항상 크거나 같은 수부터 for문을
        // 시작해 수를 고를 수 있도록 합니다
        getResult(count + 1, i);
    }
}
 
int main(void) {
    scanf("%d%d", &n, &m);
    getResult(0, 1);
    return 0;
}