[BOJ] 백준 15655. N과 M (6)

▶문제설명

[BOJ] 백준 15655. N과 M (6)

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

▶ 설계

---

[문제]

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

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

• N개의 자연수 중에서 M개를 고른 수열
• 고른 수열은 오름차순이어야 한다.

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

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

무식하게 모든 경우를 다 해보면 되는 문제입니다. (브루트 포스)

이런 식의 문제는 재귀로 구현하면 편합니다.

주어진 n개의 수 중에 아직 사용되지 않은 수를 벡터에 push_back 하면서 가능한 경우를 모두 탐색합니다.

(단, 벡터의 맨 뒤에 있는 숫자보다 큰 경우에만 push_back 한다.)

사용된 수의 인덱스를 체크하기 위해 1차원 bool 배열을 사용합니다.

벡터의 사이즈가 M이 되면 M개의 수를 선택한 것이 되므로 수열을 출력합니다.

재귀호출 전에 true, 호출 후에 false로 바꾸어주는 패턴은 브루트 포스 문제에서 늘 나오는 패턴이므로 몸에 익히는 게 좋습니다.

▶ 구현

---

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
 
bool check[9];
 
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(check[i]) continue;
        if(!vt.empty() && vt.back() >= numbers[i]) continue;
 
        check[i] = true;
        vt.push_back(numbers[i]);
 
        dfs(numbers,m,vt);
 
        check[i] = false;
        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;
}

▶ 결과

---