문제에서 얘기한대로 정수 a를 b로 바꾸려고 할 때 가능한 연산은 아래 두 가지이다.
이 문제는 bfs를 bottom-up (a에서 b로 가기 위해 계속 값을 더해감) 형식으로 풀이하면 쉽게 답을 찾을 수 있다.
먼저 큐를 준비한 뒤 정수 a를 0으로 초기화된 depth와 함께 튜플 형태로 넣어준다. (= q.append((A,depth))
) 여기서 depth는 연산 횟수를 의미하며 이를 통해 현재 값의 연산 횟수를 알 수 있다.
이후 while문을 돌며 큐에 원소가 존재한다면 원소를 pop한다.
만약 pop한 원소가 b와 같다면, a에서부터 b까지의 연산을 가장 빠르게 즉, 최소 연산으로 마친 것이므로 간주할 수 있기에 break로 멈춘 뒤 연산 횟수를 출력한다.
pop한 원소가 b가 아니라면, 아직 원소 b가 되기 위한 연산 과정이 남아있다는 뜻이므로 현재 원소에서 1) 2를 곱한 경우 와 2) 1의 수를 가장 오른쪽에 추가하는 경우 를 큐에 삽입한다. 이 때 연산 개수를 의미하는 depth를 1 증가시켜 함께 삽입하는 것을 잊으면 안된다.
만약 큐에 원소가 모두 비었는데도 답을 출력하지 못했다면 -1을 출력한다.
import sys
from collections import deque
input = sys.stdin.readline
a, b = map(int, input().split())
def bfs():
q = deque()
depth = 1
result = 0
q.append((a, depth))
while q:
n, depth = q.popleft()
if n == b:
result = depth
break
depth += 1
# 2를 곱하는 경우
cur_1 = n * 2
if cur_1 < b:
q.append((cur_1, depth))
elif cur_1 == b:
result = depth
break
# 1의 수를 가장 오른쪽에 추가하는 경우
cur_2 = n * 10 + 1
if cur_2 < b:
q.append((cur_2, depth))
elif cur_2 == b:
result = depth
break
return result
result = bfs()
if not result:
print(-1)
else:
print(result)