백준 16953 파이썬

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

16953번: A → B

 

정답 코드

from collections import deque

a, target = map(int, input().split())
queue = deque()

queue.append((a * 2, 1))
queue.append((int(str(a) + '1'), 1))

while queue:
    num, count = queue.popleft()
    if num == target:
        print(count + 1)
        exit()
    elif num > target:
        continue
    else:
        queue.append((num * 2, count + 1))
        queue.append((int(str(num) + '1'), count + 1))
print(-1)

 

유의할 점은 출력값에 1을 더해야 한다. 문제 조건에서, 연산의 최소값에 1을 더한값을 출력하라고 명시돼 있다.

 

두개의 서로 다른 연산을 적용하여 target 넘버를 맞출 때까지 반복하는 문제이다. target 넘버를 맞출 때까지 몇번의 연산을 거쳤는지 구하는 것이 문제의 핵심이다. 여기서 연산의 횟수를 count 라 하겠다.