[ 백준 16953번 ] A->B - python

문제 링크

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

16953번: A → B

 

풀이

프로그래머스 '타겟 넘버'와 유사한 문제 

https://programmers.co.kr/learn/courses/30/lessons/43165

코딩테스트 연습 - 타겟 넘버

위 문제를 풀었어서 그런지 쉽게 풀었다.

단 만들기 불가능할 때를 대비하여 큐에 삽입해 줄때 b보다 작거나 같은 수만 넣어주어야 한다. 

from collections import deque

a, b = map(int,input().split())

q = deque()

# 숫자와 인덱스 저장 
q.append((a, 1))

result = False

while q:
  num, index = q.popleft()

  if num == b:
    print(index)
    result = True
    break

  else:
  # b보다 작거나 같은 경우에만 큐에 넣어줌 
    if num * 2 <= b :
      q.append((num*2, index +1))
    if int(str(num)+'1') <= b :
      q.append((int(str(num)+'1'), index+1))

if result == False:
  print(-1)