BOJ - 15650 N과 M(2)

1. 문제 : https://www.acmicpc.net/problem/15650

2. 문제 티어: 실버3

3. 문제 유형 : 백트래킹

4. 문제 풀이 : 

N과 M 문제와 동일하지만 하나가 다른 점은 오름차순으로 정렬이 되어야 한다는 점이다.

즉 순서를 보장해야하므로 시작 포인트를 추가해서 인덱스를 지정해주어야 한다는 점이 가장 큰 차이다. 

이외 로직은 모두 동일하게 작성하면 된다, 즉 선택할 수 있는 숫자는 항상 이전에 선택한 숫자보다 커야 한다.

 

5. 문제 코드

const fs = require("fs");
let input = fs.readFileSync("/dev/stdin").toString().split("\n");
let [N,M] = input[0].split(" ").map(Number);
let arr = [];

// start index가 유지되어야 하는 recursive 함수 
function recursive(current, start, n , m) {
    // 만약 현재 단계의 배열의 길이가 M일 때
    if(current.length === m) {
        console.log(current.join(" "));
        return;
     }
     // start 부터 시작해서 인덱스를 유지시켜줌
     for(let i=start;i<=n;i++){
        // 현재 배열의 값을 추가해줌
        current.push(i);
        // 다음 재귀 함수 호출
        recursive(current, i+1 , n , m);
        // 이전 단계 되돌리기
        current.pop();
    }
}

// 실행
recursive(arr, 1, N, M);

 

6. 시간 복잡도

1<=N<=M<=8 이기 때문에 최악의 경우 N = 8 , M = 8이기 때문에 O(N!)가 될 수 있다.