[프로그래머스][dp] 숫자 변환하기

     

목차

 

 

 

 

문제

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

 

 

문제 구현 방향

bfs로 풀어도 시간 초과가 나는 문제이다. 따라서 dp로 풀어야 한다.

 

 

 

코드 구현

let dp = Array(1000001).fill(Infinity);


function solution(x, y, n) {
    dp[x] = 0;
   for(let i=x; i<=y; i++){
       if(i+n <= y){
           dp[i+n] = Math.min(dp[i]+1, dp[i+n]);
       }
       if(i*2 <= y){
           dp[i*2] = Math.min(dp[i*2], dp[i]+1);
       }
       if(i*3 <=y){
            dp[i*3] = Math.min(dp[i*3], dp[i]+1);
       }
   }
    let ans = Math.min(dp[y]);
    return isFinite(ans) ? ans : -1;
}