February 14, 2023

16953번: A → B

문제 요약

• 정수 A를 B로 다음 두 연산을 이용하여 바꾸는 최소의 경우의 수
  • 2를 곱한다.
  • 1을 수의 가장 오른쪽에 추가한다.
• 1 ≤ A < B ≤ 10^9
• 시간 제한 : 2초

풀이

from collections import deque

A, B = map(int, input().split())
visited = {}

def bfs():
    q = deque()

    q.append((A, 1))

    while (q):
        num, cost = q.pop()

        if (num == B):
            print(cost)
            return

        if (str(num) in visited):
            continue

        visited[str(num)] = True

        if (not str(num * 2) in visited and num * 2 <= B):
            q.append((num * 2, cost + 1))

        addedNum = int(str(num) + '1')
        if (not str(addedNum) in visited and addedNum <= B):
            q.append((addedNum, cost + 1))

    print(-1)

bfs()

• BFS 이용