[백준] 15650번: N과 M (2)

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

문제

알고리즘 접근 방법

dfs를 활용한 조합문제이다.

조합문제를 풀기 위해서는 간단하다.

재귀 호출에서, 현재 뽑은 원소의 이전값들은 고려하지 않게끔, for문의 i값을 함께 넘겨주면 된다.

예를 들어, 1 2 3 4 5에서 3개를 뽑을 경우,

1 2 3

1 2 4

1 2 5

1 3 4

1 3 5

1 4 5

이런식으로, 두번째 숫자는 반드시 첫번째 숫자보다 크도록, 세번째 숫자는 반드시 두번째 숫자보다 크도록 하면 된다.

풀이

#include <iostream>
#define MAX 9
using namespace std;

int N, M; 
int arr[MAX] = {0, };
bool visited[MAX] = {0, };
void dfs(int num, int cnt){
    if (cnt == M){
        for (int i=0; i<M; i++)
            cout << arr[i] << ' ';
        cout << '\n';
        return;
    }
    for (int i=num; i<=N; i++){
        if (!visited[i]){ // 방문하지 않았다면
            visited[i] = true;
            arr[cnt] = i;
            dfs(i+1, cnt+1);
            visited[i] = false;
        
        }
    }
}
int main(){

    cin >> N >> M;
    dfs(1, 0);
    return 0;
}

정리

ㅠ..ㅠ

💡 참고 포스팅

cryptosalamander님 블로그