백준 16953 A → B

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

 

 이 문제는 정수 A,B가 주어지고 A를 2를 곱하거나, 오른쪽에 1을 더하는 과정을 몇 번을 해야 B가 되는지를 출력하는 문제이다. 

 필자는 이 문제를 BFS를 응용하여 조건을 하나하나 따져가며 스택에 넣어가며 탐색을 하는 식으로 풀었다. 만약 만들어낸 숫자가 B보다 크다면 이 과정에서는 작아지는 과정이 없으므로 바로 스택에서 빼버리는 식으로 풀었다.

 

def A_to_B(A,B):

    stack = [(A,1)]
    ans = -1
    while stack:
        now,route = stack.pop()
        new1 = now*2
        new2 = int(str(now)+'1')

        if new1==B or new2==B:
            ans = route+1
            break
        if new1 < B:
            stack.append((new1,route+1))
        if new2 < B:
            stack.append((new2,route+1))
    
    return ans

A,B = map(int,input().split())

print(A_to_B(A,B))