백준 16953번: A → B (Python)

문제

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

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

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

입력

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

출력

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

 

 

---

 

풀이

그리디인걸 알고 있으면 접근 방법이 되게 쉬워지는 듯하다. A에서 B로 가는거나, B에서 A로 가는 경우나 똑같다. 그러면 B에서 A를 가는 경우는

1.  2로 나눈다
2.  1의 자리에 1이 있으면 1을 뗀다

의 반복으로 구할 수 있는데, 두 경우는 동시에 성립하지 않는다. 즉, B에서 A로 가는 경로는 (존재한다면) 유일하다. 또한, 1.과 2.가 안 되는 경우도 있는데(15같은 숫자), 이 경우에는 경로가 존재하지 않는다.

 

코드

A, B = map(int, input().split())
count = 0

while(A<B):
    if B % 2 == 0:
        B = B//2
        count += 1
    else:
        if B % 10 == 1:
            B = B // 10
            count += 1
        else:
            break

if A == B:
    print(count+1)
else:
    print(-1)