[BAEKJOON 백준] 16953 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을 출력한다.

BFS를 활용을 해서 문제를 해결했다. 모든 경우의 수를 넣어주면서 해당하는 값이 나올때까지 반복하도록 제작을 했다.

2를 곱했을 때 B보다 크지 않으면 리스트에 넣어주고, 1을 가장 오른쪽에 붙여준 후의 값이 B보다 크지 않으면 넣어주도록 했다.

 

A,B=map(int, input().split())
ans=-1
que=[A]
time=0
while len(que)>0:
    size=len(que)
    for i in range(size):
        num=que.pop(0)
        if num==B:
            ans=time+1
            break
        if num*2<=B:
            que.append(num*2)
        if int(str(num)+'1')<=B:
            que.append(int(str(num)+'1'))
    time+=1
print(ans)