[python] 백준 - 16953. A → B

🤔문제 해결

• S1 | 그래프, BFS 난 DFS

알고리즘 분류에는 그래프와 BFS로 나와있는데 잘 모르겠고, DFS로 해결했다.

목표 숫자부터 두가지 경우로 나눠서 들어간다. 

1. 맨 끝의 숫자가 1이면 1을 버리고 재귀
2. 맨 끝의 숫자가 1이 아닐 때 2로 나누어 떨어지면 2로 나누고 재귀

테스트 케이스 3번을 예시로 하겠다 ( 100, 40021 )

• 40021: 맨 끝의 숫자가 1이므로 1을 버린다 40021 => 4002
  체크하는 방법은 10으로 나눈 나머지, 버리는 방법은 10으로 나눈 몫
• 4002: 맨 끝의 숫자가 1이 아니고 2로 나누어 떨어지므로 2로 나눈다. 4002 => 2001
• 2001: 버린다. 2001 => 200
• 200: 나눈다. 200 => 100
• 100: 100 == A 이므로 그만! 과정의 횟수를 세보면 4이다.
• 답은 +1을 하므로 5

테스트 케이스 2번을 예시로 하겠다 ( 4, 42 )

• 42: 2로 나눈다. 42 => 21
• 21: 1을 버린다. 21 => 2
• 2: 2 < A 이므로 탈락!
• -1 출력

💨

💻소스 코드

def solution(A, B):
    answer = 1

    def cal(num):
        nonlocal answer
        if num > A:

            if num % 10 == 1:
                answer += 1
                cal(num // 10)
            else:
                if num % 2 == 0:
                    answer += 1
                    cal(num // 2)
                else:
                    answer = -1
                    return
        elif num < A:
            answer = -1
            return

    cal(B)
    print(answer)


if __name__ == "__main__":
    A0, B0 = map(int, input().split())
    solution(A0, B0)

 

📕문제 확인

출처: BACKJOON ONLINE JUDGE

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

16953번: A → B

---

문제

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

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

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

입력

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

출력

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