[백준/16953/파이썬] A->B

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

16953번: A → B

Problem

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

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

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

조건

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

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

SOL

DFS로 풀었다가, 메모리 초과를 맞은 문제이다.

메모리 공간을 B만큼 잡은게 원인이였던거 같다. BFS로 조건에 맞게 dq에 넣고 도는 방식으로 구현을 다시 하니까 통과가 되었다.

 

from collections import deque
import sys
input= sys.stdin.readline
A,B = map(int,input().split())

ans=-1
dq=deque([(A,1)])

while dq:
    x,cnt=dq.popleft()
    if x==B:
        ans=cnt
        break
    if 2*x<=B:
        dq.append((2*x,cnt+1))
    if 10*x+1<=B:
        dq.append((10*x+1,cnt+1))

print(ans)