백준 15657 : N과 M(8)

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

15657번: N과 M (8)

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 문제였습니다. 단, N개의 자연수는 모두 다른 수입니다. 조건은 다음과 같고,

 

- N개의 자연수 중에서 M개를 고른 수열

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

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

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

 

'15652번 N과 M(4)' 문제와 거의 비슷한 문제였고, 재귀 호출을 통해 중복을 허용하면서 항상 크거나 같은 수를 고를 수 있도록 하여 M개를 고를 때마다 수열을 출력하는 방식으로 문제를 해결했습니다.

 

 

[소스코드]

 

#include<algorithm>
#include<iostream>
using namespace std;
 
// 수열을 담을 배열 result
int n, m, num[7], result[7];
 
// 1 ~ n까지의 수 중에서 중복을 허용하여 
// 비내림차순으로 m개를 골라 출력하는 함수
void getResult(int count, int start) {
 
    // m개를 골랐다면 출력합니다
    if (count == m) {
        for (int i = 0; i < m; i++)
            cout << result[i] << ' ';
        cout << '\n';
        return;
    }
    // 0번 인덱스부터 n-1번 인덱스 중에서 하나를 골라
    // reult 배열에 인덱스에 해당하는 수를 넣습니다
    for (int i = start; i < n; i++) {
        result[count] = num[i];
 
        // 다음 수를 고르러 가는데 start에 해당하는 인자에
        // i를 넣어주어 방금 골랐던 수보다 항상 크거나 같은 수부터 
        // for문을 시작해 수를 고를 수 있도록 합니다
        getResult(count + 1, i);   
    }
}
 
int main(void) {
 
    cin >> n >> m;
    for (int i = 0; i < n; i++)
        cin >> num[i];
 
    // 수열은 사전 순으로 증가하는 수열이어야 하므로
    // 입력을 받은 뒤 오름차순으로 정렬합니다
    sort(num, num + n); 
    getResult(0, 0);
    return 0;
}