[백준 - 15666] N과 M (12) [C++]

1. 문제

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

15666번: N과 M (12)

2. 풀이과정

N과 M (11)문제에서 아래의 조건만 추가된 문제이다.

 

고른 수열은 비내림차순이어야 한다.

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

N과 M (11) 설명 : https://poisson-it.tistory.com/28

[코드설명]

N과 M (11)코드에 한줄만 추가해주면 된다.

 

dfs함수내에서 

if(v.size() && v.back() > arr[i]) continue; 로

벡터의 가장 마지막에 삽입되어 있는 원소가 현재 방문할 원소보다 크다면 

비내림차순을 만족할 수 없으므로 건너뛰어준다. 

 

3. 코드

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

using namespace std;
int n, m;
vector<int> arr;

void dfs(vector<int>& v, int depth) {
    if(depth == m) {
        for(int i=0; i<m; i++) cout << v[i] << " ";
        cout << "\n";
        return ;
    }
    bool same_level_visited[10001] = {false};
    for(int i=0; i<n; i++) {
        if(!same_level_visited[arr[i]]) {
            if(v.size() && v.back() > arr[i]) continue;
            same_level_visited[arr[i]] = true;
            v.push_back(arr[i]);
            dfs(v, depth+1);
            v.pop_back();
        }
    }
}

int main() {
    cin.tie(NULL);
    ios::sync_with_stdio(false);
    cin >> n >> m;
    for(int i=0; i<n; i++) {
        int tmp;
        cin >> tmp;
        arr.push_back(tmp);
    }
    sort(arr.begin(), arr.end());
    vector<int> v;
    dfs(v, 0);
    return 0;
}