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

📍문제 설명📍

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

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

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

---

📚입출력 예시📚

---

💯성공한 풀이💯

const solution = (x, y, n) => {
    let queue = [[y, 0]]; //y to x 거꾸로 시작
    
    while(queue.length) {
        let [num, i] = queue.shift(); // y , 횟수
        
        if(num === x) return i;
        if(num % 3 === 0 && num / 3 >= x) queue.push([num / 3, i + 1]);
        if(num % 2 === 0 && num / 2 >= x) queue.push([num / 2, i + 1]);
        if(num - n >= x) queue.push([num - n, i + 1]);
        
    }
    return -1;
}

💡문제 접근 방식💡

처음에는 최소 횟수를 구하는거여서 그리디 문제인줄 알았으나, dp 문제와도 비슷해 보였다.
보통 x -> y 로 가는 문제는 거꾸로도 생각해야한다. 그래서 y -> x 로 생각했다.

처음에는 계속 시간초과가 나서 왜 안풀리지 생각했는데 push 할때 배열을 잘못 넣고 있었다.

코드 진행방식을 설명하면

queue = [[40, 0]]

queue = [[20, 1], [35, 1]]

queue = [[35, 1], [10, 2], [15, 2]]

queue = [[10, 2], [15, 2], [30, 2]]
return 2

계산한 값을 queue에 계속 넣으면서 x와 같아지면 return을 한다.
if 문을 통해 모든 조건이 걸러지므로, 가장 먼저 x와 같아지면 최소 횟수를 구할 수 있다.