[그리디] Python - 16953번, A → B(A to B)

import sys
input = sys.stdin.readline


def dfs(num, cnt):
    if num == B:
        global Min
        if Min == -1:
            Min = cnt
        else:
            Min = min(Min, cnt)
        return

    nextNum = num*2
    if nextNum <= B:
        dfs(nextNum, cnt+1)
    nextNum = int(str(num)+'1')
    if nextNum <= B:
        dfs(nextNum, cnt+1)


A, B = map(int, input().split())
Min = -1
dfs(A, 1)
print(Min)

 

다음 그림은 만약 입력값이 '2 41'로 들어왔다고 했을 때의 설명이다.

기본적으로 dfs를 통해 1. num*2 2. int(str(num)+'1')일 때를 탐색해주는데, 그 값이 B보다 크면 dfs를 하지 않는다.

결국 dfs에 들어온 num이 우리가 찾고 있는 B와 일치하면 전역변수 Min을 수정해준다.