문제

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

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

입력

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

출력

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

예제 입력 1

2 162

예제 출력 1

5
2 → 4 → 8 → 81 → 162

예제 입력 2

4 42

예제 출력 2

-1

예제 입력 3

100 40021

예제 출력 3

5

코드

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

def dfs(a,b):

    stack=[]
    stack.append((a,1))

    min=100000

    while stack:
        n,i=stack.pop()
        if n <= b:
            if n==b:
                if min>i:
                    min=i

            else:
                stack.append((n*10+1,i+1))
                stack.append((n*2,i+1))

    return min

result=dfs(a,b)

if result ==100000:
    print(-1)
else:
    print(result)

• 필요한 연산의 최솟값을 구하는 문제이므로 즉 최소 깊이의 수를 구하는 문제라고 생각이 들었습니다.

• 그렇기에 깊이우선인 문제 특성을 생각해 bfs보다 dfs가 어울리다고 생각하였고 dfs로 구현했습니다.

• 재귀 보다 stack으로 구현이 더 빠를 것같아서 스택으로 구현했습니다.