백준 15657 N과 M(8)

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

15657번: N과 M (8)

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

using namespace std;

int n, m;

vector<int> arr;
vector<int> ans;


void dfs(int k, int cnt) {

    ans.push_back(k);

    if (cnt == m) {

        for (int i = 0; i < cnt; i++) {
            cout << ans[i] << " ";
        }
        cout << "\n";

        ans.pop_back();
        return;
    }

    for (int i = 0; i < n; i++) {
        if (k <= arr[i]) {
            dfs(arr[i], cnt + 1);
        }
    }

    ans.pop_back();




}

int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);



    cin >> n >> m;


    for (int i = 0; i < n; i++) {
        int temp;
        cin >> temp;
        arr.push_back(temp);
    }

    sort(arr.begin(), arr.end());

    for (int i = 0; i < n; i++) {
        dfs(arr[i], 1);
    }




    return 0;
}

 

입력을 받고, 수열이 비내림차순이어야 하므로 정렬을 한 뒤, 각 요소들에 대하여 dfs를 돌린다.

ans에 배열의 순서를 저장하고, 각 dfs에 전체 배열을 도는 동안 다음에 올 숫자가 비내림차순 조건을 만족하면 재귀적으로 dfs를 돌린다.

해당 배열의 크기가 m에 도달하면 그 배열을 출력한다.