[JavaScript/백트래킹] 백준 실버 3 : 15652 - N과 M (4)

 

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

15652번: N과 M (4)

---

📌 작성한 코드

// 15652
const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "Beakjoon/Silver/test.txt";
const input = fs.readFileSync(filePath).toString().trim();

const [N, M] = input.split(" ").map(Number);
const arr = new Array(M);
let answer = "";

const backTracking = (at, depth) => {
    if (depth === M) {
        answer += `${arr.join(" ")}\n`;
        return;
    }

    for (let i = at; i <= N; i++) {
        arr[depth] = i;
        backTracking(i, depth + 1);
    }
};

backTracking(1, 0);
console.log(answer);

 

📌 설명 

중복이 가능하고, 비 내림차순(중복된 숫자가 포함된 숫자들의 오름차순)대로 나열되어야 한다.

그래서 중복을 허용하기 위해 이전에 방문한 숫자를 기록하는 방문 배열을 사용하지 않고, 현재 숫자부터 그 이상의 숫자만 탐색할 수 있도록 at 인수를 사용해서 탐색 시작할 숫자를 재귀 함수에 전달해준다.

 

N과 M(2)번 문제에서는 오름 차순만 인정해서 해당 숫자에 +1을 해서 숫자 초과인 숫자만 탐색하도록 했던 것과 아주 유사하다.

 

 

✅ 성공