[BaekJoon] 24268 번 2022는 무엇이 특별할까? 문제 - (nodejs)

문제 번호 :  24268 번

문제 바로가기 ☞ https://www.acmicpc.net/problem/24268

---

 

<<< 문제 내용 >>>

---

 

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

let [N, M] = input[0].split(" ").map(Number);
let combArr = [];
let visited = new Array(M).fill(false);
let answer = [];

const comb = (cnt, arr) => {
  if (cnt === M) {
    if (arr[0] === "0") return;
    combArr.push(arr);
    return;
  }

  for (let i = 0; i < M; i++) {
    if (!visited[i]) {
      visited[i] = true;
      comb(cnt + 1, arr + i);
      visited[i] = false;
    }
  }
};

comb(0, "");

combArr.forEach((el) => {
  let temp = 0;

  for (let j = 0; j < M; j++) {
    temp += el[j] * M ** (M - 1 - j);
  }

  answer.push(temp);
});

console.log(answer.find((el) => el > N) || -1);

* 백준 대회인 Hello, BOJ 2022! 의 1번 문제이다.

 

중복되지 않는 수들로 이루어진 n진수를 이용해서 값을 구하는 문제이다.

일단 이 문제를 보자마자 n진수의 범위가 1~9인 것을 보고, 백트래킹으로 풀면 되겠다 싶었다.

 

백트래킹이 손에 익어서 그런지 이제는 1분안에 쉽게 구현할 수 있었다.

그 외에는 각 조합들을 전부 숫자로 바꿔주었고, find를 이용해 숫자를 찾고, 찾지 못하면 -1을 출력했다.

 

더 빠르게 하고자 한다면 find 대신 이진 탐색을 이용하여 찾으면 되겠다.

 

 

 

도움이 되셨다면 공감 부탁드립니다.