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

 

class : 3

level : silver 3

문제 링크 : 1로 만들기

1463번: 1로 만들기

 

My Solution

let fs = require('fs');
let input = fs.readFileSync('/dev/stdin').toString().trim();
const N = parseInt(input);
let dp = new Array(N+1).fill(0);
dp[2] = 1;
dp[3] = 1;
dp.forEach((value,index)=>{
    if(index>3){
        let temp = [dp[index-1]];
        index%2===0?temp.push(dp[index/2]):0;
        index%3===0?temp.push(dp[index/3]):0;
        dp[index] = Math.min(...temp)+1;
    }
})
console.log(dp[N]);

 

느낀점

처음에는 Greedy 알고리즘을 떠올릴 수 있지만 Dynamic Programming 문제였다. 반례로는 22라는 숫자를 들 수 있다.

이전에도 비슷한 문제를 보았기에 어렵지 않았다.