백준[node.js] > 1463번 1로 만들기

문제

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

 

문제풀이

dp로 접근하지 않으면 시간초과가 나는 문제였다.

 

문제풀이의 핵심은 아래 점화식이다. 

여기서 dp[i] 는 i를 만들기 위해서 필요한 연산 횟수이다. ( dp[1]=0, dp[2]=1, dp[3]=1 이다 )  

 

1 ) i가 3의배수이고 2의 배수일 때

dp[i] = Math. ( dp[i/3] +1 , dp[i/2] +1 , dp[i-1] +1 )   

 

2 ) i가 3의 배수이고 2의 배수가 아닐때

dp[i] = Math. ( dp[i/3] +1 , dp[i-1] +1 )   

 

3 ) i가 2의 배수이고 3의 배수가 아닐때

dp[i] = Math. ( dp[i/2] +1 , dp[i-1] +1 )   

 

 

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

let num = Number(input);

if (num === 1) {
    console.log(0);
    return;
}

let dp = Array(num + 1).fill(Infinity);
dp[1] = 0;
dp[2] = 1;
dp[3] = 1;

for (let i = 4; i <= num; ++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[num]);