BOJ - 15651 N과 M(3)

1. 문제 링크 : https://www.acmicpc.net/problem/15651

2. 문제 티어 : 실버3

3. 문제 유형: 백트래킹

4. 문제 풀이

1) N과 M(1) , N과 M(2)에 이은 백트래킹으로 길이가 M인 수열을 구하는 문제 시리즈이다.

2) 같은 수를 여러 번 골라도 된다는 조건이 있기에 start 혹은 i+1 등으로 인덱스를 부여할 필요가 없으며

3) 하나의 계산을 끝내고 그 다음 계산을 할 때 이전 선택과 관계 없이 n까지 모두 돌려도 된다는 뜻이다. 

4) 3) 과 같이 할 시 console.log로 출력값을 찍는 부분에서 시간 초과가 이루어질 수 있으니 미리 새로운 배열에 문자열을 생성해서 한 번에 출력하여 백준의 시간 초과 문제를 해결하는 방법이다.

5) 기존 (1)과 (2) 에서는 console.log를 수열 하나를 완성할 때마다 console.log를 출력해줬으나 지금은 모든 결과를 메모리(result 배열)에 저장한 후, 한 번만 출력한다.

 

5. 문제 코드

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

let result = [];
function recursive(current, n, m) {
    if (current.length === m) {
        // 결과를 문자열로 저장
        result.push(current.join(" "));
        return;
    }
    for (let i = 1; i <= n; i++) {
        current.push(i);
        recursive(current, n, m); // 중복 선택 가능
        current.pop();           // 백트래킹
    }
}

recursive([], N, M);
console.log(result.join("\n"));