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

문제

 

---

풀이

 

myunji.tistory.com/73?category=1154147

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

이 문제를 약간 응용한 문제이다.

오름차순을 구현하려면 어떻게 해야할까? 현재 노드의 값을 기억해두면 될 것이다.

---

소스코드

 

#include <iostream>

using namespace std;
const int MAX = 8;

int N, M;
int arr[MAX];

void backNM(int cnt, int flag) { //오름차순 위해 현재 노드 저장하는 flag 추가
    if (cnt == M) { //배열 끝까지 완성하면 출력
        for (int i = 0; i < M; i++)
            cout << arr[i] << ' ';
        cout << '\n';
    } else {
        for (int i = flag; i < N; i++) {
            arr[cnt] = i + 1;
            backNM(cnt + 1, i + 1); //가지 아래로 내려감
        }
    }
}

int main() {
    cin >> N >> M;
    backNM(0, 0);
}

이전 문제와 달리 visited 배열이 빠졌다.

배열 {1, 2, 3, 4}가 있다고 해보자. 당연히 1부터 2, 3, 4 순으로 탐색이 이루어 질 것이다. 우리는 현재 노드보다 큰 수만을 필요로 하는데 이것들은 당연히 unvisited일 것이다. 그렇기 때문에 굳이 visited 배열이 없어도 백트래킹이 가능한 것이다.

설명을 잘 못해서 말이 좀 이상해 보일 수 있는데 간단하게 설명하면 현재 노드를 기억하는 flag자체가 visited 배열의 역할을 대신한다고 보면 된다.