[백준] N과 M (4)_15652

길이가 K인 수열 A가 있을 때, A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하는 비내림차순 수열을 모두 구해야 한다.

같은 수를 여러번 골라도 되므로 코드는 3번 문제와 거의 유사하고, 비내림차순 수열을 만들기 위해서 다음과 같은 부분을 추가했다. 

if(!v.empty()) {

            if (v[v.size() - 1] > i + 1) {

                continue;

            }

        }

v에 이미 자연수가 들어가 있다면, 새로 넣으려는 수와 v의 마지막 요소를 비교한다. v의 마지막 요소가 더 크다면 비내림차순 수열이 아니므로 그냥 패스한다. 

#include <iostream>
#include <vector>
using namespace std;
 
int M, N;
vector<int> v;
 
void print() {
    for (int i = 0; i < M; i++) {
        cout << v[i] << " ";
    }
    cout << "\n";
}
 
//길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK
void dfs(int cnt) {
    if (cnt == M) {
        print();
        return;
    }
    for (int i = 0; i < N; i++) {
        if(!v.empty()) {
            if (v[v.size() - 1] > i + 1) {
                continue;
            }
        }
        v.push_back(i+1);
        dfs(cnt + 1);
        v.pop_back();
    }
}
 
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);
    cin >> N >> M;
    v.clear();
    dfs(0);
    return 0;
}