[백준 / BOJ] - 15650번 N과 M(2) C++ 풀이

 

---

 

백준 - 단계별로 풀어보기 [15650] 

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);
}

 

 

평가

 

15649번이 dfs를 통한 순열 구하기였다면, 이번 문제는 dfs를 통한 조합 구하기라고 할 수 있다.

for문의 index값을 함께 재귀함수의 인자로 넘겨주면 앞에서 이미 찾은 조합은 다시 뽑지 않도록 만들 수 있다.