[Python] 백준 16953번: A → B

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

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

풀이

• a가 b보다 작으면 현재까지의 연산 횟수를 count로 넘겨주면서 mulTwo 또는 addOne 수행.
• a가 b와 같아지기 전까지 계속 수행해야 하므로 b보다 작은 수행결과는 큐에 다시 넣어줌.
• 최소 횟수이므로 heapq로 구현

그리디

import sys
import heapq

input = sys.stdin.readline
a , b = map(int,input().split())

def mulTwo(a, count):
    return count+1, a*2

def addOne(a, count):
    return count+1, int(str(a)+"1")

def solution(a, b):
    q = [(0, a)]
    while q:
        cnt, a = heapq.heappop(q)
        if a<b:
            heapq.heappush(q, mulTwo(a, cnt))
            heapq.heappush(q, addOne(a, cnt))
        elif a==b:
            return cnt+1
        else:
            continue
    return -1

print(solution(a, b))

BFS

import sys
from collections import deque

input = sys.stdin.readline


def solution(a, b):
    q = deque([(a, 1)])

    while q:
        a, cnt = q.popleft()
        if a == b:
            print(cnt)
            return

        if a * 2 <= b:
            q.append((a * 2, cnt + 1))
        if a * 10 + 1 <= b:
            q.append((a * 10 + 1, cnt + 1))
    print(-1)


a, b = map(int, input().split())
solution(a, b)