알고리즘/BOJ

[BOJ 16953, Python 3] A → B

70825 2021. 8. 7. 20:40
반응형

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

 

16953번: A → B

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

www.acmicpc.net

 

풀이

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

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

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

 

 

코드

1
2
3
4
5
6
7
8
9
10
11
12
13
A, B = map(int, input().split())
= __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)
cs
반응형