[백준] 16953번 A → B - Python / 알고리즘 중급 2/3 - 브루트 포스 - 문제 (연습)

---

---

---

💡 문제

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

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

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

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

출력

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

---

💭 접근

이 문제는 간단한 DFS 문제로,

주어진 수 a에 2를 곱하는 연산과,

next = num * 2
if next <= b:
    dfs(next, depth + 1)

뒤에 1을 추가하는 연산의 경우 a에 10을 곱한 뒤 1을 더해주는 것으로 구현할 수 있다.

next = num * 10 + 1
if next <= b:
    dfs(next, depth + 1)

이후, a가 b와 같아지면 연산횟수 (depth + 1)를 출력하고, 만들 수 없다면 -1을 출력하면 된다.

---

📒 코드

import sys

def dfs(num, depth):
    if num == b:
        print(depth + 1)
        sys.exit()

    next = num * 2
    if next <= b:
        dfs(next, depth + 1)
    
    next = num * 10 + 1
    if next <= b:
        dfs(next, depth + 1)

a, b = map(int, input().split())

dfs(a, 0)

print(-1)

---

💭 후기

오랜만에 간단한 DFS 문제였다.

---

🔗 문제 출처

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

---