❓ Problem

1로만들기 문제와 비슷하다 다만 주어지는 숫자 와 목표값이 있다.

🤔 How

• bfs 로 문제에 접근하여 풀었다.
• 구하고자하는수는 최소 몇번으로 target numbr에 도착하는지를 구한다. (depth)

❗ Solve

# A → B
import sys
from collections import deque
input = sys.stdin.readline


def bfs(start_number, target_number):
    q = deque()
    q.append((start_number, 1))
    answer = -1
    while q:
        n, d = q.popleft()
        if n == target_number:
            answer = d
        else:
            if 2*n <= target_number:
                q.append((2*n, d+1))
            n_plus1 = int(str(n)+"1")
            if n_plus1 <= target_number:
                q.append((n_plus1, d+1))
    return answer


if __name__ == "__main__":
    start_number, target_number = map(int, input().split())
    print(bfs(start_number, target_number))