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

---

 

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

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

문제

 

 

 

풀이

 

15651번 N과 M (3)에서의 코드에다가  15650번 N과 M (2)에서 사용했던 for문의 i값을 재귀함수의 매개변수로 넘겨주는 방식을  합치면 풀이가 가능하다.

잘 이해가 안갈 경우, 이전 글과의 코드 차이점을 보면 이해가 가능할 것이다.

 

 

코드

 

#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++)
    {
            visited[i] = true;
            arr[cnt] = i;
            dfs(i,cnt+1);
            visited[i] = false;
    }
}

int main() {
    cin >> n >> m;
    dfs(1,0);
}

 

 

평가

 

N과 M 4문제는 각각 순열, 조합을 dfs를 활용하여 푸는 방법을 배울 수 있는 문제이다.

백트래킹의 기본인 재귀 설계에 대해 짚고 넘어가면 좋을 것 같다.