[Programmers / JS] 154538번 - 숫자 변환하기

Problem

문제 보기

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

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

---

Solution

function solution(x, y, n) {
    if (x === y) return 0;
    let answer = 1000000;
    
    function dfs (num, count) {
        if(num === x) {
            answer = Math.min(answer, count);
            return;
        } else if (num < x) return;
        
        if(num % 3 === 0) dfs(num / 3, count + 1);
        if(num % 2 === 0) dfs(num / 2, count + 1);
        dfs(num - n, count + 1);
    };
    
    dfs(y, 0);
    return answer === 1000000 ? -1 : answer;
}

dfs가 떠올라서 풀었더니 효율성 시간 초과났다..😿

시간 초과 줄이는 방법을 고민하다가 답이 안 나와서 다른 사람의 코드를 확인해보니 dp를 이용하였다.

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