[boj] 1463. 1로 만들기 (node.js)

문제 요약

[boj] 1463. 1로 만들기 (node.js)

• 입력으로 들어오는 정수 X에 대해 가능한 연산들은 아래와 같다. (1 <= X <= 10^6)

  • 3으로 나누어 떨어지면 -> 이 수를 3으로 나눈다
  • 2로 나누어 떨어지면 -> 이 수를 2로 나눈다
  • 1을 뺀다

• 연산을 활용해 주어진 정수 X를 1로 만들 수 있는 최소 횟수는?

풀이

• 시간 제한이 0.15초인 동적 프로그래밍 문제다.
• 입력 정수 X의 범위가 주어졌으므로 (1 <= X <= 10^6) 미리 dp 배열을 채워둔 후 입력값에 대한 결과를 출력해주면 된다.
• X를 1로 만드는 최단 경로를 파악하는 문제와 같으므로, 동적 프로그래밍으로 풀기 위해 거꾸로 생각하면 1부터 X를 만드는 문제다. 따라서 낮은 수부터 dp 배열을 채운다.
• 점화식은 해당 조건을 만족할 때마다 값을 이전 횟수 + 1로 갱신시키도록 하며,
• 조건을 만족한 이후에도 다음 조건에서 더 짧은 거리를 가질 수 있으므로 각각의 조건을 독립적으로 둔다. (if - if - )

내 풀이

const readline = require("readline");
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const solution = () => {
  let dp = [0, 0];
  const X = input();
  run(2);
  console.log(dp[X]);

  function run(n) {
    while (n <= 1000000) {
      if (n % 3 == 0) {
        dp[n] = dp[n / 3] + 1;
      }
      if (n % 2 == 0) {
        if (!dp[n]) dp[n] = dp[n / 2] + 1;
        dp[n] = Math.min(dp[n], dp[n / 2] + 1);
      }
      if (!dp[n]) dp[n] = dp[n - 1] + 1;
      dp[n] = Math.min(dp[n], dp[n - 1] + 1);
      n++;
    }
  }
};

let line = 0;
const input = () => stdin[line++];

let stdin = [];
rl.on("line", function (line) {
  stdin.push(line);
}).on("close", function () {
  solution();
  process.exit();
});