백준 16953 <A -> B> Python

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

16953번: A → B

---

2를 곱한 수와 10을 곱하고 1을 더한 수가 같을 수 없다는 점을 착안하고 목적수에 도달만 하면 무조건 리턴하게 하면 됩니다. 처음에는 dp 를 사용하려 했지만 메모리 초과때문에 저장하지 않고 비교만 해야합니다.

---

from collections import deque

def solution(A, B):

    # 큐

    queue = deque([[A, 1]])

    # 계산

    while True:

        # 큐가 비면 끝

        if not queue:

            return -1

        # 현재 수, 카운트

        now_num, cnt = queue.popleft()

        # 목적수에 도달하면 리턴

        if now_num == B:

            return cnt

        # 메모 비교 및 최신화

        # x2

        if now_num*2 <= B:

            # 큐에 추가

            queue.append([now_num*2, cnt + 1])

        # x10 + 1

        if now_num*10 + 1 <= B:

            # 큐에 추가

            queue.append([now_num*10 + 1, cnt + 1])

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

print(solution(A, B))