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

문제 설명

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

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

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

---

제한사항

• 1 ≤ x ≤ y ≤ 1,000,000
• 1 ≤ n < y

---

입출력 예

x|y|n|result
10|40|5|2
10|40|30|1
2|5|4|-1

---

입출력 예 설명

입출력 예 #1

• x에 2를 2번 곱하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #2

• x에 n인 30을 1번 더하면 40이 되고 이때가 최소 횟수입니다.

입출력 예 #3

• x를 y로 변환할 수 없기 때문에 -1을 return합니다.

---

나의 풀이

기존 풀이

const times = []
    function dfs(time, num) {
        if(num === y) {
            times.push(time)
            return
        } else if (num > y) {
            return
        }
        dfs(time+1, num+n)
        dfs(time+1, num*2)
        dfs(time+1, num*3)
        
        return
    }
    
    dfs(0, x)
    
    if(!times.length) return -1
    return Math.min(...times)

효율성 시간초과, 정해진 수를 구할 때 *로 접근하기 보다 /의 개념으로 접근하는 것이 더 효율적이다.

수정된 풀이

function solution(x, y, n) {
    if(x>=y) return 0
    // 모든 경우의 수를 Infinity로 두고 변환에 걸린 수를 입력
    const dp = Array(y+1).fill(Infinity)
    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] === Infinity ? -1 : dp[y]
}