백준 - N과 M (4) :15652 번

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

15652번: N과 M (4)

이번문제는 N과 M (2)와 유사하다. 단, 중복 가능하다. 

아래 문제 조건과 같이 앞의 수가 다음수보다 작거나 같다은 조건을 만족하면 된다.

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

 

따라서 N과 M (2)에서 재귀함수의 첫번째 인자만, i+1이 아니랑 i를 주면 된다.

즉, i값을 포함해서 다음 수를 정해나가는 형태이다. 왜냐? 중복을 허용하기 때문이다.

 

#include <bits/stdc++.h>
using namespace std;
vector <int> nm;
void NM4(int, int, int);

int main() {
    int n, m;
    cin >> n >> m;
    NM4(1, n, m);
    return 0;
}
void NM4(int s, int n, int m) {
    if (nm.size() == m) {
        for (int i = 0; i < m; i++) {
            cout << nm[i] << " ";
        }
        cout << '\n';
        return;
    }
    for (int i = s; i <= n; i++) {
        nm.push_back(i);
        NM4(i, n, m); //현재 nm vector에 넣은 수 이후 수를 확인 한다. (오름차순)
        nm.pop_back();
    }
}