[BOJ] 백준 15652. N과 M (4)

▶문제설명

[BOJ] 백준 15652. N과 M (4)

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

▶ 설계

---

[문제]

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

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

문제에서 N과 M (1)과 다른점은 진한 글씨로 표시된 부분 밖에 없습니다.

N과 M(1) 풀이 링크 ( https://it-earth.tistory.com/138 )

비내림차순의 수열이란 1 2 2 3 4 4 4 5 6 7 와 같이, 

'오름차순' 또는 '같은 숫자가 연속'되는 수열을 말합니다.

N과 M (1)의 풀이와 거의 같지만

같은 수를 여러 번 골라도 되므로 중복 체크를 할 필요가 없고,

1부터 N까지의 자연수 중에서 벡터의 끝에 있는 원소보다 크거나 같은 경우만 push_back하고 재귀호출하도록 구현해야합니다.

▶ 구현

---

#include<iostream>
#include<vector>
using namespace std;
 
void dfs(int N, int M, vector<int>& vt){
    if(vt.size() == M){
        for(int i: vt)
            cout<<i<<" ";
        cout<<"\n";
        return;
    }
 
    for(int n=1; n<=N; n++){
        if(!vt.empty() && vt.back() > n) continue;
 
        vt.push_back(n);
        dfs(N,M,vt);
        vt.pop_back();
    }
}
int main(){
    int N,M;
    vector<int> vt;
    cin>>N>>M;
    dfs(N,M,vt);
    return 0;
}

▶ 결과

---