Baekjoon [16953] A → B - python

문제

정수 A를 B로 바꾸려고 한다. 가능한 연산은 다음과 같은 두 가지이다.

2를 곱한다.
1을 수의 가장 오른쪽에 추가한다.
A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

출력

A를 B로 바꾸는데 필요한 연산의 최솟값에 1을 더한 값을 출력한다. 만들 수 없는 경우에는 -1을 출력한다.

예제 입력 1

2 162

예제 출력 1

5

예제 입력 2

4 42

예제 출력 2

-1

예제 입력 3

100 40021

예제 출력 3

5

문제 코드

from collections import deque

start_num ,target_num = map(int,input().split())

num_dict = {}
que = deque()
first_num = start_num * 2
second_num = int(str(start_num)+"1")
cnt = 1
que.append((start_num,cnt))

while que:
    number, cn = que.popleft()
    # print(number)
    if number > target_num: # 만약 뽑은 숫자가 이미 타겟넘버를 지나갔으면
        pass
    else:
        first_num = number * 2
        second_num = int(str(number) + "1")

        if first_num == target_num or second_num == target_num: # target number랑 같으면
            print(cn+1)
            break
        elif first_num < target_num or second_num < target_num: # 숫자가 작을 때
            if first_num not in num_dict:
                tn = cn + 1
                num_dict[first_num] = tn
                que.append((first_num,tn))

            elif first_num in num_dict:
                tn = cn + 1
                if num_dict[first_num] > tn:
                    num_dict[first_num] = tn

            if second_num not in num_dict:
                kn = cn + 1
                num_dict[second_num] = kn
                que.append((second_num, kn))
            elif second_num in num_dict:
                tn = cn + 1
                if num_dict[second_num] > tn:
                    num_dict[second_num] = tn
        else: # 숫자가 클 때
            if len(que) > 0:
                continue
else:
    print(-1)


# print(num_dict)

문제 해석

기본적으로 모든 값에 x2와 1을 이어붙인다. 이때 해당 숫자가 target num을 도착하면 break로 출력.

타겟 넘버보다 작다면 지속적으로 deque에 append를 하면서 이를 dict를 통해 cnt 변수를 저장 및 기록한다.

이후 타겟넘버보다 클경우 deque안에 있는 값중에 타겟넘버가 될수도 있으니 다 비워질때까지 continue를 진행. 이때도 다 비워진다면 else문으로 -1을 출력한다.