[lv2] 16956. A → B(Python 파이썬 풀이)

출처

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

16953번: A → B

결과

문제

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

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

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

입력

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

출력

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

예제 입력 1

121
1231
12421
0

예제 출력 1

2 162

예제 입력 2

4 42

예제 출력 2

-1

예제 입력 3

100 40021

예제 출력3

5

해석

a에서 b로 바꾸는데 2가지 연산이 있다. 하나는 2를 곱하는 것이고, 하나는 10을 곱한뒤 1을 더한 것이다. while문을 사용하면 되는 것이지만, 연산 과정에서 수가 너무 커지지 않도록 조심해야한다. 연산 결과가 목표값인 b보다 크지 않도록 하면 결과는 구할 수 있을 것이다. flag를 설정하여 while 문에 빠져나가도 b에 값이 해당되지 않는 경우 -1을 출력하도록 해주었습니다.

소스 코드

import sys
from collections import deque
sys.stdin = open("19653in.txt", 'r')
 
a,b = map(int, sys.stdin.readline().split())
li = deque([(0, a)])
flag = 1
point = 0
ba = set([a])
while 2 ** point < b and li:
    point, a = li.popleft()
    if a == b:
        flag = 0
        print(point + 1)
        break
    if not (a*10 + 1) in ba and ((a*10 + 1) <= b):
        ba.add(a*10 + 1)
        li.append((point+1, a * 10 + 1))
    if not (a*2) in ba and (a * 2 <= b):
        ba.add(a*2)
        li.append((point+1, a * 2))
if flag:
    print(-1)