A → B ( 16953 )

16953번: A → B

 

나의 풀이

import sys

def _dfs(B, n_num, n_ct):
    answer = float('inf')
    if n_num >= B:
        if (n_num == B):
            return n_ct
        else:
            return float('inf')
    else:
        answer = min(answer, _dfs(B, n_num * 2, n_ct + 1))
        answer = min(answer, _dfs(B, int(str(n_num) + '1'), n_ct + 1))
    return answer

def _main(A, B):
    answer = _dfs(B, A, 1)
    if (answer == float('inf')):
        return -1
    return answer

A, B = map(int, sys.stdin.readline().rstrip().split())
print(_main(A, B))

 

시간 복잡도

_dfs(B, n_num, n_ct) : 조건 만족시 까지 dfs 알고리즘, 깊이가 늘어날수록 2**(n) 횟수 수행
해당 알고리즘 시간 복잡도 : 지수형 시간 복잡도 ( 2**len(str(B)) )