백준 15650 - N 과M(2) [C/C++]

https://www.acmicpc.net/problem/15650

문제 설명과 입력 및 출력 설명

 

 중복 없이 1부터 N까지의 자연수 중에서 M개를 선택하면 된다. 즉, 오름차순 순열을 모두 출력하면 되는 것이다.

 

 우선 첫 번째 뽑히는 수는 다음부터 뽑히는 수 보다 무조건 작아야 하므로, 오름차순으로 들어있는 벡터 자료구조를 쉽게 떠올릴 수 있다. 거기서부터 하나씩 뽑으면서 인덱스를 증가시켜 나간다면, 구현이 될 것이라 생각했다.

 

 이 때 인덱스를 접근한 수가 뽑힐 수도 있고, 안 뽑힐 수도 있다. 중복을 허용하지 않으므로 접근된 수에 대한 경우의 수는 2가지 뿐이 없으므로, 이를 따로 재귀적으로 불러주어 처리해주면 된다.

 

 아래는 C++로 작성된 코드이다. 

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int last, howmany;

void Comb(vector<int> arr, vector<int> result, int r, int idx, int depth){
    if(r==howmany){
        for(int i=0;i<result.size();i++){
            cout << result[i] << " ";
        }
        cout << '\n';
    }
    else if (depth==arr.size()){return;}
    else{
        result[idx] = arr[depth];
        Comb(arr, result, r+1, idx+1, depth+1);

        Comb(arr, result, r, idx, depth+1);
        
    }
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> last >> howmany;

    vector<int> arr, result;

    for (int i=0;i<last;i++){arr.push_back(i+1);}
    for (int i=0;i<howmany;i++){result.push_back(0);}

    Comb(arr,result,0,0,0);
    
    return 0;
}