https://www.acmicpc.net/problem/16953
문제
정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.
- 2를 곱한다.
- 1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.
입력
첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.
출력
A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.
예제 입력 1 복사
2 162
예제 출력 1 복사
5
2 → 4 → 8 → 81 → 162
예제 입력 2 복사
4 42
예제 출력 2 복사
-1
예제 입력 3 복사
100 40021
예제 출력 3 복사
5
100 → 200 → 2001 → 4002 → 40021
import collections
start , end = map(int,input().split())
mincount = float('inf')
count = 0
queue = [(start,0)]
queue = collections.deque(queue)
while queue:
now , count = queue.popleft()
if now == end:
if count < mincount:
mincount = count
if now * 10 + 1 <= end:
queue.append((now*10+1,count+1))
if now * 2 <= end:
queue.append((now*2,count+1))
if mincount == float('inf'):
print(-1)
else:
print(mincount+1)함수를 이용해서 구현해도 되지만 queue로 이용해서 풀어보았다