[BOJ] 백준 16953번 A를 B로 바꾸기 (A->B) - 파이썬(Python)

문제

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

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

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

입력

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

출력

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

 

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

16953번: A → B

 

💡 풀이 및 코드

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

count = 0
while b > a:
    if b % 10 == 1:
        b //= 10
    elif b % 2 == 0:
        b /= 2
    else :
        break
    count += 1

if a == b:
    print(count + 1)
else:
    print(-1)

  A를 B로 바꿀 때는 2를 곱하거나 오른쪽에 1을 추가할 수 밖에 없으므로 B는 A보다 항상 크다. 따라서, B가 A보다 클 때 동안 B의 끝자리가 1이면 1을 떼어주고, B가 2로 나누어 떨어지는 짝수이면 2로 나눠준다. 두 가지 연산이 모두 불가능할 때는 바로 반복문을 빠져나온다. 반복문(while)이 끝나고 A와 B가 같은 수라면 연산횟수인 count에 1을 더해 출력하고, 그렇지 않다면 A는 B로 바꿀 수 없음을 의미하므로 -1을 출력한다.