[백준] 1463 1로 만들기 - javascript

📌 문제

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

📌 풀이

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

let n = Number(input[0]);
let dp = new Array(n + 1).fill(0);

// dp[i] = i가 되는데 필요한 연산의 최소값

for (let i = 2; i <= n; i++) {
  dp[i] = dp[i - 1] + 1;
  if (i % 2 === 0) {
    dp[i] = Math.min(dp[i / 2] + 1, dp[i]);
  }
  if (i % 3 === 0) {
    dp[i] = Math.min(dp[i / 3] + 1, dp[i]);
  }
}
console.log(dp[n]);

✔ 알고리즘 : DP

✔ dp[i] = i가 되는데 필요한 연산의 최소값으로 정의

✔ i를 2부터 시작해서 n까지 증가시키며 dp값을 갱신한다.

✔ i-1에서 1을 더한값을 dp값에 넣고 2,3으로 나누어떨어지는 경우 dp[i/2] + 1 과 dp[i/3] + 1 값과 dp[i]값을 비교하여 최소값을 넣어준다

✔ 난이도 : 백준 기준 실버3