[백준 16953번] [🥈2] A → B (python)

백준 사이트 링크

문제

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

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

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

입력

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

출력

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

예제 입력 1

2 162

예제 출력 1

5

2 → 4 → 8 → 81 → 162

예제 입력 2

4 42

예제 출력 2

-1

예제 입력 3

100 40021

예제 출력 3

5

100 → 200 → 2001 → 4002 → 40021

---

문제를 풀면서 막혔던 부분

bottom-up 대신 top-down으로 푸는 것이 더 효율적이다. 2를 곱하는 조건 보다 뒤에가 1인 조건을 없애는 방법을 먼저 작성해야 된다.

코드

ver(1)

a, b = map(int,input().split())
result = 1
while(a!=b):
  result += 1
  temp = b
  if b % 10 == 1:
    b //= 10
  elif b % 2 == 0:
    b //= 2

  if temp == b:
    print(-1)
    break
else:
  print(result)