백준 16953번: A → B (파이썬)

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

16953번: A → B

 

문제

 

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

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

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

 

입력

 

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

 

출력

 

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

 

풀이

 

가장 처음 든 생각은 A부터 BFS로 탐색하는 것이었다.

하지만 이 방법은 반드시 시간 초과가 발생할 것이라 판단하였고, B에서부터 두 가지 연산의 역연산을 수행하는 코드를 떠올렸다.

우선 B를 포함해야 하므로 cnt = 1로 초기화한다.

 

역연산을 수행하며 B가 0에 도달하는 경우는 A를 지나쳐 왔다는 뜻이고, 다시 말해 불가능한 경우므로 -1을 출력한다.

또한 B가 A와 같아졌을 때는 cnt를 출력하도록 한다.

 

B에서 A가 될 수 있는 경우는 마지막 자리수가 1인 경우와, 짝수인 경우가 있다.

단순히 생각하면 두 경우를 제외한 경우는 모두 A가 될 수 없다.

따라서 두 경우에 적절한 역연산을 수행하며, cnt를 증가시킨다. 

 

소스 코드

 

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

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