16953. A → B

업데이트 시간 : 2023-02-16 07:06:48 +0000

[Silver II] A → B - 16953

문제 링크

성능 요약

메모리: 34528 KB, 시간: 88 ms

분류

너비 우선 탐색(bfs), 그래프 이론(graphs), 그래프 탐색(graph_traversal), 그리디 알고리즘(greedy)

문제 설명

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

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

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

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 10⁹)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

💡 Solutions

📄 A → B.py

from collections import deque
N, M = map(int,input().split())

que = deque()

def bfs(start, end):
    que.append((start,0))

    while que:
        now, depth = que.popleft()

        if now > end:
            continue
        if now == end:
            return depth+1

        x1 = now*10 + 1
        x2 = now *2
        que.append((x1,depth+1))
        que.append((x2,depth+1))
    return -1

print(bfs(N,M))