백준 15652 - N과M (4) [C/C++]

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

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

예제 입력 및 출력 예시

 

 중복을 허용하므로 여러모로 생각해야 할 부분이 조금 더 생겨난 문제이다.

 

 우선 기존에 우리가 문제를 풀던 방식은, 순서대로 오름차순으로 삽입한 벡터 내에서 index 접근을 통해 뽑아내는 것이었다. 이 때 중복을 허용하지 않으므로, depth의 크기를 1씩 계속 증가시키면 그만이었는데, 이번에는  중복을 허용하니 이전의 원소를 다시 뽑을 경우도 생각해야 한다.

 이 때 필자는 depth+1을 어느 경우는 하지 말아야 한다는 생각을 바로 떠올리지 못했는데, 그걸 깨닫고 이 문제를 2분만에 풀었을 때는 엄청난 허망감 아닌 허망감(?)이 들었다... 열심히 알고리즘 짜며 생각을 좀 더 떠올려야 할 필요성을 느꼈다.

 

 기존에 포스팅한 N과M (2) 문제의 알고리즘과 코드는 매우 똑같으며, depth+1 => depth로만 고쳐주면 동작하는 간단한 알고리즘이다.

백준 15650 - N 과M(2) [C/C++] — 예비 대학원생의 Computer Science 저장소 (tistory.com)

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

 

 

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

using namespace std;

int howmany, last;

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);

        Comb(arr, result, r, idx, depth+1);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    vector<int> arr, result;  

    cin >> last >> howmany;
    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;
}