[Python] BOJ 16953 Greedy / A -> B

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

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

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

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

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

입력 예시
2 162

출력 예시
5

문제 해결 포인트

작은 수에서 큰 수를 만드는 가장 적은 횟수 류의 문제를 풀 때는 작은 수 -> 큰 수로 가는게 아니라
큰 수 -> 작은 수로 가는게 푸는데 용이하다.

1. 테스트 케이스는 모두 통과했는데 자꾸 시간 초과가 나서 당황스러웠던 문제.
   빠뜨린 테스트 케이스가 있나 찾아보니 3 30인 경우를 통과해야했다. 당시 짠 코드에 3 30을 넣어보니 무한 루프에 빠졌다.
2. 2로 나누어 떨어지는 경우, 길이가 1이상이고 맨 뒷 글자가 1인 경우로만 코드를 짰는데 맨 앞에 둘 다에 해당하지 않는 경우 멈춘다는 조건식을 넣어줬어야 했다.

코드

# Greedy 16953 A->B
# A -> B 로 바꾸는 연산의 최솟값에 1을 더한값 출력하기

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

while a < b : 
    if b % 2 != 0 and str(b)[-1] != '1' :               # 2로 나누어 떨어지지도 않고, 마지막 글자가 1도 아닐 경우
        break
    elif str(b)[-1] == '1' and len(str(b)) > 1 :        # 마지막 글자가 1이고, b의 길이가 1보다 클 경우
        tmp = str(b)
        b = int(tmp[:len(tmp)-1])
        cnt += 1
    elif b % 2 == 0 :                                   # 2로 나누어 떨어지는 경우
        b = b // 2
        cnt += 1

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