백준 16953 : A → B (Python)

백준 16953 문제

문제

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

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

입력

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

출력

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

예제 입력 1

2 162

예제 출력 1

5

---

나의 풀이

A에서 2가지 연산을 반복해 B를 찾는 알고리즘은 B가 언제 어디서 나올지 알 수 없어 시간복잡도 측면에서 비효율적인 알고리즘일 것이다. 따라서 B가 루트 노드인 포화 이진 트리에서 말단 노드가 A인 경로를 찾아가는 방식으로 알고리즘을 구현했다. 예제 입력 1의 경우 아래의 그림과 같은 포화 이진 트리를 구성할 수 있다. 이 때 x로 표기된 노드는 애초에 연산이 불가능해 방문할 수 없으므로 최적 구조를 만족한다고 볼 수 있다. 따라서 A -> B를 찾는 문제를 B -> A로 역추적해 그리디 알고리즘으로 구현하는 문제이다.

import sys 

def check(target,curr):
    num = 0 
    while(True):
        if curr == target:
            num+=1
            break 
        elif (curr > target and curr%2==0):
            curr = curr//2
            num+=1
        elif (curr > target and curr %10 ==1):
            curr = curr//10
            num+=1
        else:
            num = -1 
            break 
    return num
    

A, B = map(int,sys.stdin.readline().split())

answer = check(A,B)
print(answer)