[Programmers] 숫자 변환하기 - level 2

문제 설명

자연수 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	50	2
10	40	30	1
2	5	4	-1

 

---

나의 풀이

from collections import deque


def solution(x, y, n):
    # BFS를 통해 타겟 숫자 추적
    q = deque()
    q.append(x)

    checked = [-1] * (y + 1)
    checked[x] = 0

    while q:
        cur = q.popleft()

        if cur == y:
            return checked[cur]

        if cur + n <= y and checked[cur + n] == -1:
            checked[cur + n] = checked[cur] + 1
            q.append(cur + n)

        if cur * 2 <= y and checked[cur * 2] == -1:
            checked[cur * 2] = checked[cur] + 1
            q.append(cur * 2)

        if cur * 3 <= y and checked[cur * 3] == -1:
            checked[cur * 3] = checked[cur] + 1
            q.append(cur * 3)

    return -1