16953(A → B) - 해결

A → B

 

문제

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

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

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

 

입력

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

 

출력

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

---

2배와 뒤에 1이 붙는 방법 밖에 없기 때문에 줄어드는 경우는 없다.

그래서 숫자가 타겟보다 크다면 넘기고 작을땜나 신경 쓰는 방법을 썼다.

import sys
input = sys.stdin.readline
from collections import deque

A, B = map(int,input().split())
# q 생성
q = deque([(A,0)])

# bfs
# 숫자가 작아지는 건 없기 때문에 작은 수들 중에서만
# 신경쓰는 방식을 사용
while q:
    # 숫자와 카운트
    num, cnt = q.popleft()

    # B에 도착하면 카운트 + 1하고 빠져나옴.
    if num == B:
        ans = cnt + 1
        break

    # 2배
    if num * 2 <= B:
        q.append((num*2,cnt+1))
    # 뒤에 1추가
    if int(str(num) + "1") <= B:
        q.append((int(str(num) + "1"),cnt+1))
# 없으면 -1
else:
    ans = -1
print(ans)