[JS][프로그래머스 -LEVEL 2 -숫자변환하기]

문제

경우의 수를 찾는 문제로써 처음에는 dfs으로 풀었더니 시간 오류가 나게 되었다.

그래서 dp 문제로 변경하였다.

해결

• 새로운 함수를 만들고 infinity 로 채워놓는다.
• x부터 시작해서 y 까지 될수 있는 경로중 작은 경우로 바꿔서 다시 돈다.

코드

function solution(x, y, n) {
    const dp = new Array(y+1).fill(Infinity);
    dp[x] = 0;
    for(let i=x; i<=y; i++){
        dp[i+n] = Math.min(dp[i+n],dp[i]+1);
        dp[i*2] = Math.min(dp[i*2],dp[i]+1);
        dp[i*3] = Math.min(dp[i*3],dp[i]+1);
    }
    return dp[y]!==Infinity? dp[y] : -1;
}