[백준] 1463번 1로 만들기 (JavaScript)

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

1463번: 1로 만들기

// const input = require("fs").readFileSync("/dev/stdin").toString().trim().split("\n");
let input = require("fs")
  .readFileSync("example.txt")
  .toString()
  .trim()
  .split("\r\n");

let x = parseInt(input.shift());
const dp = new Array(x + 1).fill(0);
for (let i = 2; i <= x; i++) {
  dp[i] = dp[i - 1] + 1;
  if (i % 3 === 0) {
    dp[i] = Math.min(dp[i], dp[i / 3] + 1);
  }
  if (i % 2 === 0) {
    dp[i] = Math.min(dp[i], dp[i / 2] + 1);
  }
}
console.log(dp[x]);

숫자가 커질수록 작은 숫자에 의존하는 dp성 문제이다. 

예를 들어 4의 경우는 (3에서 1로가는 경우의수 + 4가 3으로 가는 경우의 수)이다. 

따라서 나눴을 경우와 그냥 이전의 숫자에 의존하는 경우를 비교하여 작은 경우의 수로 채워 넣으면 된다.