[BaekJoon] 16953 A → B (Silver 2) - Python

문제

 

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다. 

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

---

입출력 예시

 

입력: 첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

출력: A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

 

입력예시1)

2 162

출력예시1)

5

2 → 4 → 8 → 81 → 162

 

입력예시2)

4 42

출력예시2)

-1

 

입력예시3)

100 40021

출력예시3)

5

100 → 200 → 2001 → 4002 → 40021

---

코드

from collections import deque

a, b = map(int, input().split())

def bfs(start):

    q = deque([])
    q.append([start, 1])
    ret = -1

    while q:
        num, cnt = q.popleft()
        if num > b: continue
        if num == b:
            ret = cnt
            break

        n1 = num * 2
        q.append([n1, cnt + 1])

        n2 = (num * 10) + 1
        q.append([n2, cnt + 1])

    return ret

print(bfs(a))

---

실행 화면

 

---

채점 결과