[Python] 백준 16953번 A -> B

문제

16953번: A → B

입력

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

출력

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

입력 예제

2 162

4 42

출력 예제 

5

-1

문제 풀이

• Top-down 방식으로 접근하는게 연산하기 더 편할 것 같아 Top-down으로 접근했다.
• 2로 나누거나, 뒷자리에서 1을 빼는 두 가지 연산 중 뒷자리가 1인 경우는 2로 나누어 떨어지지 않고, 2의 배수인 경우 뒷자리의 수가 1이 아니므로, 뒷자리 수가 1인 경우 1을 빼고, 2의 배수인 경우 2로 나눈 후 연산 횟수를 카운트
•  2의 배수도 아니고, 1로 끝나지도 않아 위 두 경우에 속하지 않는 경우 (1, 17)과 같은 경우 while문 탈출
• 모든 연산이 끝난 후, a와 b의 값이 다르다면 b로 a를 만들 수 없다는 뜻이므로 -1을 출력

코드

a, b = map(int,input().split())
cnt = 1
while b > a:
    if b % 2 == 0:
        b //= 2
        cnt += 1
    # 끝자리가 1일 때
    elif b % 10 == 1:
        b //= 10
        cnt += 1
    else:
        break
if b != a:
    print(-1)
else:
    print(cnt)