[BOJ/C++] 15650번 : N과 M(2)

오늘은 저번에 이어서 N과 M 두번째 문제를 풀어보겠다. 이 역시도 백트레킹을 쓸 것이다

 

N과 M(1)과 비슷하지만, 다른 점을 생각해보면 오름차순이어야 된다 즉, (1)에서는 1 2 2 1이 가능했지만 이 문제에선 2 1은 취급할 수 없다

이를 고려해서 코드를 짜보자

#include <iostream>
using namespace std;

int N, M;
int arr[9];  // 선택한 숫자를 저장할 배열
bool visited[9];  // 방문 여부 체크

void backtrack(int depth, int start) {
    if (depth == M) {  // M개의 숫자를 선택했으면 출력
        for (int i = 0; i < M; i++) {
            cout << arr[i] << " ";
        }
        cout << "\n";
        return;
    }

    for (int i = start; i <= N; i++) {  // 현재 숫자부터 시작하여 오름차순 유지
        if (!visited[i]) {
            visited[i] = true;  // 사용 표시
            arr[depth] = i;  // 현재 숫자 선택
            backtrack(depth + 1, i + 1);  // 다음 숫자는 i+1 이상부터 선택
            visited[i] = false;  // 백트래킹 (원상 복구)
        }
    }
}

int main() {
    cin >> N >> M;
    backtrack(0, 1);
    return 0;
}

오름차순으로 정렬해야되므로, 시작하는 숫자를 기억하기 위해 (1)과 다르게 인자를 하나 더 추가해줬다. 이를 통해 사용을 표시하고,, 숫자 선택하고,, 재귀를 통해 시작 숫자를 늘리고,, 해서 배열을 출력한다