[Programmers] 숫자 변환하기 / Python, 파이썬 / 154538

https://school.programmers.co.kr/learn/courses/30/lessons/154538

프로그래머스

문제 설명

문제 설명

자연수 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

---

입출력 예xynresult

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합니다.

문제 풀이

from collections import deque

def solution(x, y, n):
    dis = [0 for _ in range(y + 1)]
    q = deque([x])
    if x == y:
        return 0
    
    while q:
        val = q.popleft()
        for i in range(3):
            if i == 0:
                cur_val = val * 2
            if i == 1:
                cur_val = val * 3
            if i == 2:
                cur_val = val + n
            if cur_val > y or dis[cur_val]:
                continue
            if cur_val == y:
                return dis[val] + 1
            q.append(cur_val)
            dis[cur_val] = dis[val] + 1
    
    return -1