[BOJ][⚪2][백준#16953] A → B

문제 출처

BAEKJOON Online Judge #16953

문제

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

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

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

입력

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

출력

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

예제

예제 1

입력

2 162

출력

5

예제 2

입력

4 42

출력

-1

예제 3

입력

100 40021

출력

5

My Sol

from collections import deque

def main():
    a, b = map(int, input().split())
    Q = deque()
    Q.append((a, 0))


    while Q:
        k, cnt = Q.popleft()
        if k == b: return cnt+1
        if k > b: continue
        Q.append((int(str(k)+'1'), cnt+1))
        Q.append((k*2, cnt+1))
    return -1

print(main())

간단한 문제였다. deque에 넣으며 두 가지 경우를 모두 체크하면 되겠다. deque에 넣고 FIFO 방식으로 뽑아내기 때문에 뽑아낸 값이 b인 경우의 cnt+1이 답이 된다.

결과

맞았습니다!!