백준 16953번 - A -> B

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
1. 2를 곱한다.
2. 1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

# 틀린코드

1을 수의 가장 오른쪽에 추가하는 연산때문에 string으로 처리하였다. 1을 오른쪽에 추가하는게 최소 10배이상 커지는 거니까 2를 곱하는 것보다 먼저 연산하도록 하였다(greedy적인 생각).
처음엔 A에서 B로 가게 코드를 짜봤는데 예외가 많아보여 B에서 A로 가는 것을 생각하였다. 이건 좀 잘 생각해낸듯? 근데 테스트케이스는 다 통과했는데 정답은 아니였다. 논리상 문제가 없는데 틀렸다는 건 생각못한 예외가 있다는 것이다. 문제에서 놓친 게 없다면 이 경우 알고리즘이 틀렸을 가능성이 높다. 예외를 추가적으로 처리하기보단 다른 방법을 찾는게 나을 것 같았다.

import sys

input = sys.stdin.readline

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

while int(A) < int(B):
  if B[-1] == "1":
    B = B.replace(B[-1], '')
    count += 1
  elif int(B) % 2 == 0:
    B = B.replace(B, str(int(B)//2))
    count += 1
  else:
    break

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

# 정답코드

1을 오른쪽에 추가해야되면 무조건 string으로 해야된다고 생각했는데 생각해보니 1을 추가하는 거니깐 10으로 나눈 나머지가 1 인 수로 생각하면 되지 않을까? 방금 떠올렸을 때도 10배이상 커진다했다. 0을 붙이면 10배 커지는 거니깐 1을 붙이면 10배 커지는 수의 1 더한 수...맞네?
아이디어를 잡으니 금방 정답을 찾았다. 역시 그리디는 아이디어 싸움인듯!!

import sys

input = sys.stdin.readline

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

while A < B:
  if B % 10 != 1 and B % 2 != 0:
    break
  if B % 10 == 1:
    B = B // 10
    count += 1
  elif B % 2 == 0:
    B = B // 2
    count += 1

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