A → B

문제

백준 16953번 문제
https://www.acmicpc.net/problem/16953

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

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

[입력]
첫째 줄에 A, B (1 ≤ A < B ≤ 10^9)가 주어진다.

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

풀이

• 주어진 숫자에서 1을 붙이거나 2를 곱해나가며 B에 도달하면 출력을 한다.
• BFS로 쉽게 풀 수 있을거 같았다.
  • 2씩 곱하거나 1씩 붙여나가면 계산 도중 반복되지 않을까 싶었는데 단조증가이며 먼저 도달하여 출력이 되므로 생각할 필요가 없었다.
• BFS queue를 많이 사용하고 python이기 때문에 deque를 사용하겠다.
  • 배열은 pop, push가 O(1)이 아니기 때문에 사용하지 않는다.

코드

import sys
from collections import deque
import heapq

input = sys.stdin.readline

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

q = deque([(a,1)])

while(q):
    tmp,cnt = q.popleft()

    if tmp == b:
        print(cnt)
        exit()
    tmp1 = tmp*2
    tmp2 = tmp*10 + 1
    
    if tmp1 <= b:
        q.append((tmp1, cnt+1))
    if tmp2 <= b:
        q.append((tmp2, cnt+1))
print(-1)