백준 16953번 A->B

문제

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

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

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

입력

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

출력

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

 

N=list(map(int,input("").split()))

count=0

while(N[0]!=N[1]):

    tmp=N[1]
    count+=1
    if N[1]%10==1:
        N[1]=N[1]//10

    elif N[1]%2==0:
        N[1]=N[1]//2


    if N[1]==tmp:
        print("-1")
        break



if N[1]!=tmp:

    print(count+1)

 

bottom -up을 사용하는것보다 top-down 을 사용하였습니다.