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

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

1463번: 1로 만들기

 

<코드>

let input = require("fs").readFileSync("/dev/stdin").toString();

let num = Number(input);

const DP = new Array(num + 1).fill(0);

for (let i = 2; i <= num; i++) {
  DP[i] = DP[i - 1] + 1;

  if (i % 2 === 0) {
    DP[i] = Math.min(DP[i], DP[i / 2] + 1);
  }
  if (i % 3 === 0) {
    DP[i] = Math.min(DP[i], DP[i / 3] + 1);
  }
}

console.log(DP[num]);

 

<풀이방법>

DP문제로 반대로 생각하여 1부터 시작하여 num이 되는 경우로 구한다.

1을 빼는 것은 1을 더 해주는 것이니까 DP[i] = DP[i-1] +1 이 되고

3으로 나누어 떨어지면 3으로 나누는 것은 3으로 나누어떨어지면 3을 곱하면 된다.

DP[3]의 경우 DP[1] 에서 3을 곱한 경우와 DP[3]을 비교해야하므로 DP[i/3]+1, DP[3]을 비교하는 식을 짜면 된다.

 

끝