백준: 16953 A → B

문제

16953번: A → B

 

문제 풀이

 정수 A를 B로 바꾸기 위해 2가지 방법을 사용한다.

• A에 2를 곱한다.
• A의 가장 오른쪽에 1을 추가한다.

 이때, B로 바꾸는데 필요한 연산의 최솟값을 구하는 문제이다. 이는 `DFS`를 통해 `2를 곱하는 경우`와 `오른쪽에 1을 추가하는 경우`에 대해 가지를 뻗어나가면 쉽게 구할 수 있다.

 

코드

from sys import stdin


def dfs(sub_total, cur_depth):
    # B보다 큰 경우, 가지치기
    if sub_total > B:
        return

    if sub_total == B:
        print(cur_depth)
        exit(0)
        return

    # 2를 곱하는 경우
    dfs(sub_total * 2, cur_depth + 1)
    # 오른쪽에 1을 더하는 경우
    dfs(int(str(sub_total) + '1'), cur_depth + 1)


if __name__ == "__main__":
    A, B = map(int, stdin.readline().split())

    dfs(A, 1)
    print(-1)