[알고리즘/백준/18511] 큰 수 구성하기(Nodejs, DFS)

문제

---

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

18511번: 큰 수 구성하기

 

풀이

---

const fs = require("fs");
const filePath = process.platform === "linux" ? "/dev/stdin" : "./input.txt";
let [n, arr] = fs.readFileSync(filePath).toString().trim().split("\n");

const [N, K] = n.split(" ").map(Number);
const nums = arr.split(" ").map(Number);
nums.sort((a, b) => a - b);
let answer = 0;

// DFS
function DFS(L, num) {
  if (num > N) return;
  else {
    for (let i = 0; i < K; i++) {
      answer = Math.max(num, answer);
      DFS(L + 1, 10 * num + nums[i]);
    }
  }
}

DFS(0, 0);
console.log(answer);

N보다 작거나 같은 자연수 중에서 집합 K의 원소로만 구성된 가장 큰 수를 구하는 문제이다. 

이때 동일한 숫자를 계속 사용할 수 있다. 

 

K는 1~3자리이므로 입력에 따라 K번의 for문을 반복해서 돌면서 하나씩 숫자를 선택해 순열을 구성하고, N보다 커지면 return한다.

 

N보다 작은 경우에는 여전히 숫자를 더 뽑을 수 있다는 뜻이기 때문에 현재 저장된 answer과 비교해 최댓값이라면 answer에 저장한다.

그 다음 DFS를 통해 한 레벨 더 내려가서 다음 숫자를 뽑는다.

이때 현재 숫자에 10을 곱하고 다음 숫자를 더해주면서 숫자를 추가한다. 

예를 들어, 현재 숫자가 75이고, 다음 숫자가 5라면 75*10 + 5 = 755를 만들 수 있다.