[BOJ] 백준 15657. N과 M (8)

▶문제설명

[BOJ] 백준 15657. N과 M (8)

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

▶ 설계

---

[문제]

N개의 자연수와 자연수 M이 주어졌을 때, 아래 조건을 만족하는 길이가 M인 수열을 모두 구하는 프로그램을 작성하시오. 

N개의 자연수는 모두 다른 수이다.

• N개의 자연수 중에서 M개를 고른 수열
• 같은 수를 여러 번 골라도 된다.
• 고른 수열은 비내림차순이어야 한다.
  • 길이가 K인 수열 A가 A1 ≤ A2 ≤ ... ≤ AK-1 ≤ AK를 만족하면, 비내림차순이라고 한다.

 중복되는 수열을 여러 번 출력하면 안된다.

N과 M (5) 문제와 거의 같은 문제입니다.

진하게 표시된 

'같은 수를 여러 번 골라도 된다' 라는 조건과 

'고른 수열은 비내림차순이어야 한다' 라는 조건이 추가되었습니다.

[N과 M (5) 풀이 바로가기]

 : https://it-earth.tistory.com/143

N과 M (5) 문제에서는 나왔던 수를 체크하면서 수가 중복되지 않도록 해주었는데

그 부분을 삭제하고, 고른 수를 담는 벡터의 가장 뒤에 있는 수보다 작거나 같은 숫자만 push_back하도록 구현하면

이 문제의 정답이 된다.

▶ 구현

---

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
void dfs(const vector<int>& numbers, int m, vector<int>& vt){
    if(vt.size() == m){
        for(int n : vt)
            cout<<n<<" ";
        cout<<"\n";
        return;
    }
 
    for(int i=0; i<numbers.size(); i++){
        if(!vt.empty() && vt.back() > numbers[i]) continue;
 
        vt.push_back(numbers[i]);
        dfs(numbers,m,vt);
        vt.pop_back();
    }
}
 
int main(){
    int n,m;
    vector<int> numbers, vt;
    cin>>n>>m;
    for(int i=0,k; i<n; i++){
        cin>>k;
        numbers.push_back(k);
    }
    sort(numbers.begin(), numbers.end());
    dfs(numbers,m,vt);
    return 0;
}

▶ 결과

---