[백준] #16953 A->B (python)

16953번: A → B (acmicpc.net)

16953번: A → B

문제

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

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

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

입력

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

출력

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

 

예제 입력1

2 162

예제 출력1

5

 

예제 입력2

4 42

예제 출력2

-1

 

# Code

import sys

input = sys.stdin.readline
a, b = map(int,input().split())

count = 1
while True:
    if a == b:
        break
    elif a>b:
        count=-1
        break
    elif b%10 == 1:
        b//=10
        count+=1
    elif b%2 == 0:
        b//=2
        count+=1
    else:
        count=-1
        break
print(count)

# Comment

A->B 만들기가 문제지만, 거꾸로 생각해서 B->A가 되는 횟수를 계산하였다. B를 처음에 10으로 나눈 나머지가 1인 것을 체크하고 다음으로 2로 나눈 나머지가 0인것들을 체크하여 B를 계속 수정하여 A에 도달하도록 했다. 

예전에 제출했던 풀이가 있길래 봤더니 양방향 큐를 이용한 풀이였다. 아마 어딘가에서 알고리즘 강의 같은걸 들을 때 풀었던 것 같은데 그 방식으로도 한 번 다시 풀어봐야겠다.. 앞으론 좀 오전이나 오후 중에 알고리즘 문제를 풀도록 노력해야겠다.. 새벽엔 머리가 안돌아간다.. ㅠ