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

문제

자연수 x를 y로 변환하려고 합니다. 사용할 수 있는 연산은 다음과 같습니다.

• x에 n을 더합니다
• x에 2를 곱합니다.
• x에 3을 곱합니다.

자연수 x, y, n이 매개변수로 주어질 때, x를 y로 변환하기 위해 필요한 최소 연산 횟수를 return하도록 solution 함수를 완성해주세요. 이때 x를 y로 만들 수 없다면 -1을 return 해주세요.

 

접근

dp로 문제를 해결하였습니다.

x에서 y까지 가는법을 찾아야 하기 때문에 dp를이용해 밑에값부터 하나씩 해결주었습니다.

---

코드

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;
}

---

주의

아무 처리 없이 dfs로하면 런타임에러가 납니다.