백준 1463 — 1로 만들기: 최소 연산 횟수 구하기

D[k] = ?
3으로 나누어지면 3으로 나누거나 (D[k] = D[k/3] + 1)
2로 나누어지면 2로 나누거나 (D[k] = D[k/2] + 1)
1을 빼거나 (D[k] = D[k-1] + 1), 이들 중에서 최솟값이 D[k]가 된다.

D[1] = 0 -> 이것만 정의해줘도 점화식이 도는데에는 문제가 없다. (D[k-1]만 알면되니까)
 
D[2] = 1 (/2)
 
D[3] = 1 (/3)

const fs = require('fs');
const filePath = process.platform === 'linux' ? '/dev/stdin' : './input.txt';
 
const N = Number(fs.readFileSync(filePath, 'utf-8'));
 
const DP = Array.from({ length: 1000000 + 1 }).fill(0);
 
// 초기값 정의
DP[1] = 0;
DP[2] = DP[3] = 1; // 이 코드는 반복문을 4부터 시작하므로 필요하다.
 
// 점화식을 포함하는 for문 작성
for (let i = 4; i <= N; i++) {
    let min = Infinity;
 
    if (i % 2 === 0) {
        min = Math.min(min, DP[i / 2] + 1);
    }
    if (i % 3 === 0) {
        min = Math.min(min, DP[i / 3] + 1);
    }
    min = Math.min(min, DP[i - 1] + 1);
 
    DP[i] = min;
}
 
console.log(DP[N]);