알고리즘/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())
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)
|
cs |
반응형