악곱 == 악성곱슬

그리디

---

해당 문제는 2가지의 연산이 적용된다.

• 2배 곱하기
• 뒤에 1 붙이기 == 10곱하고 1 더하기

해당 문제를 그리디로 접근한 정당성은 다음과 같다.

• A를 B로 바꾸려고 하면 생각해야 할 것이 너무 많다. 따라서 B를 A로 바꾸는 방향으로 생각했다.
• B기준으로 아래와 같이 연산을 수정할 수 있다.
  • 2로 나누기
  • 1빼고 10으로 나누기
• 두 연산을 해야 하는 상황이 같은 겹치는 경우가 없다. → -1로 빼고 10으로 나누기의 경우는 숫자의 끝자리가 1인 경우에만 가능하다. 그리고 2로 나누기는 짝수인 경우에만 가능하다. 따라서 어떤 임의의 숫자에서 두 연산을 두고 고민할 필요가 없다. 각 상황에 맞는 연산을 하면 되기 때문에 각 상황에 최적의 판단(그리디)을 해주면 된다.

코드는 아래와 같다.

import sys

def solution(a, b):
    answer = -1
    cnt = 1
    while b > a:
        if b % 2 == 0:
            b //= 2
            cnt += 1
        elif b % 10 == 1:
            b -= 1
            b //= 10
            cnt += 1
        else:
            break
    if a == b:
        answer = cnt
    return answer

if __name__ == "__main__":
    A, B = map(int, sys.stdin.readline().rstrip().split())
    print(solution(A, B))