[백준 16953번] A → B - 파이썬(python)

https://www.acmicpc.net/problem/16953

문제

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

2를 곱한다.
1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

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

출력

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

풀이 설계

• q에 가능한 연산의 계산 값과 연산 횟수를 같이 저장한다.
• 입력받은 b와 값이 같다면 break하고 flag를 1로 바꾼다.
• 마지막까지 b와 같은 수를 만들지 못한다면 -1을 출력한다.

풀이

from collections import deque

a, b = map(int, input().split())
flag = 0
q = deque([(a, 1)])
while q:
    num, cnt = q.popleft()
    if num == b:
        print(cnt)
        flag = 1
        break
    if num * 2 <= b:
        q.append((num * 2, cnt + 1))
    if (num * 10) + 1 <= b:
        q.append(((num * 10) + 1, cnt + 1))
if not flag:
    print(-1)