[BOJ] 백준 15650. N과 M (2)

▶문제설명

[BOJ] 백준 15650. N과 M (2)

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

▶ 설계

---

[문제]

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

• 1부터 N까지 자연수 중에서 중복 없이 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

중복되는 수열을 여러 번 출력하면 안되며, 각 수열은 공백으로 구분해서 출력해야 한다.

수열은 사전 순으로 증가하는 순서로 출력해야 한다.

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

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

N과 M (1)의 풀이와 거의 같지만 오름차순인 순열만 출력되게 하기 위해서,

1부터 N까지의 정수 중에서 벡터의 끝에 있는 원소보다 작은 정수만 push_back하고 재귀호출하도록 구현해야합니다.

▶ 구현

---

#include<iostream>
#include<vector>
using namespace std;
 
bool check[9];
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(check[n]) continue;
        if(!vt.empty() && vt.back()>n) continue;
 
        vt.push_back(n);
        check[n] = true;
 
        dfs(N,M,vt);
 
        vt.pop_back();
        check[n] = false;
    }
}
int main(){
    int N,M;
    vector<int> vt;
    cin>>N>>M;
    dfs(N,M,vt);
    return 0;
}

N과 M(1) 풀이에서

진하게 표시된 코드 한 줄만 추가하면 정답이 됩니다.

▶ 결과

---