[BOJ 16953, Python 3] A → B

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

16953번: A → B

 

풀이

log2(10^9)를 해보면 그렇게 큰 수가 나오지 않는 것을 알 수 있습니다.

그래서 걍 큐에 현재 숫자에 2배를 한 수, 현재 숫자의 뒤에 1을 붙인 수를 넣어주고, B값이 나오면 출력을 해주면 됩니다.

그러나 큐에 있는 원소가 다 빠져나갈 때까지 B를 찾지 못하였으면 -1을 출력해주면 됩니다.

 

 

코드

A, B = map(int, input().split())
q = __import__('collections').deque([[A, 0]])
 
while q:
    x, y = q.popleft()
    if x == B:
        print(y + 1)
        exit()
    arr = [2 * x, int(str(x) + '1')]
    for nx in arr:
        if nx <= B:
            q.append([nx, y+1])
print(-1)