[백준/BOJ] 16953 - A → B

16953 - A -> B

📌 문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

• 2를 곱한다.
• 1을 수의 가장 오른쪽에 추가한다.

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

📋 코드

from collections import defaultdict
from collections import deque

def bfs(start, visited):
    q = deque()
    q.append(start)
    visited[start] = 1

    while q:
        x = q.popleft()
        if x == B:
            return visited[x]

        for i in (x * 2, int(str(x) + '1')):
            if 0 <= i <= int(1e9) and not visited[i]:
                q.append(i)
                visited[i] = visited[x] + 1
    return -1


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

print(bfs(A, visited))

💡 한마디

리스트를 만들어서 풀면 메모리 초과가 뜰 것 같아 딕셔너리를 이용했다. BFS를 통해 두 가지 연산을 수행하며 A를 B로 바꾸는 연산의 최솟값을 구했다.

16953번: A → B