[백준] 15649번 N과 M(1)

문제 링크 : https://www.acmicpc.net/problem/15649

문제

문제 이해

입력으로 N M이 들어온다. 1~N 까지의 숫자 중에서 M만큼 뽑아서 숫자를 나열하는 것이다. 그리고 모든 경우의 수를 내림차순으로 출력하는 문제이다.

문제 접근

1. 모든 경우의 수를 찾기
2. 찾은 값들을 내림차순으로 정렬하기.

DFS로 접근을 하였다. M만큼 뽑을 때까지 노드를 계속해서 탐색을 하고, 만약 M만큼 뽑았다면, 뽑았던 순서대로 출력을 하였다. 이렇게 한다면 내림차순과 모든 경우의 수를 탐색한다는 조건을 만족 할 수 있다.

코드 구현(c++)

#include <iostream>
#include <vector>

using namespace std;

int N,M;
int check[9]= {false,};
vector<int> result;

void dfs(int count){
    if(M == count){
        for(int i = 0 ; i < M ; i++){
            cout << result[i] << " ";
        }
        cout << "\n";
    }
    else{
        for(int i = 1 ; i <= N ; i++){
            if(!check[i]){
                result.push_back(i);
                check[i] = true;
                dfs(count + 1);
                check[i] = false;
                result.pop_back();
            }
        }
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    
    cin >> N >> M;

    dfs(0);
}

평가

최근에 푼 브루트포스 문제를 dfs로 풀고있다. 이번 문제를 봤을 때 처음에 가장 먼저 생각 난 방법은 for문 여러 개로 돌리는 방법이였다. 하지만, 해당 방법은 너무 많은 시간이 든다는 것을 깨닫고 빠르게 dfs로 풀었다.
동일한 유형의 문제를 푼다는 것은 해당 유형을 빠르게 익힌다는 점에서 장점이 존재한다. 하지만, 조금 지루한면도 없자나 있고, 다른 유형의 문제를 풀다가 맞딱뜨렸을 때, 바로 dfs로 푸는 게 생각날지는 의문이다. 조금씩 유형을 섞어가면서 풀어가야겠다.