[실버 2] 백준 16953 - A → B (파이썬)

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

풀이

정수 A를 B로 만들기 위해 사용할 수 있는 연산은

1. A → A * 2
2. A → A * 10 + 1

최소한의 연산 횟수로 A를 B로 만들고 싶다. 만들 수 없다면 -1을 출력.

이 코드는 B에서 A로 거꾸로 줄여나가는 방식

왜냐하면 A에서 B로 모든 경우를 시도하면 탐색 공간이 매우 커질 수 있기 때문

주요 아이디어

• B를 줄여가면서 A가 될 수 있는지 확인한다.
• 가능한 줄이는 방법
  • B % 10 == 1 → 끝자리가 1이면 B // 10
  • B % 2 == 0 → 짝수면 B // 2
  • 그 외에는 더 이상 줄일 수 없으므로 중단

코드

# 백준 16953 - A -> B
# 분류 : 그래프

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

while B > A :
    if B % 10 == 1 :
        B //= 10
    elif B % 2 == 0 :
        B //= 2
    else :
        break
    count += 1

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