[파이썬]백준 16953 A -> B

링크

백준 16953 A -> B

2를 곱하거나
오른쪽에 1을 추가하는 ( *10 + 1) 모든 경우의 수를 만들었다.
재귀를 통해 트리를 만들어서 완전탐색을 했다.
모든 경우의 수를 돌다가 계산한 숫자가 계산해야할 숫자보다 큰 경우 해당 트리에선 탐색을 멈췄다.

정답 코드

def cal(a, b, cnt):
    global ans
    if a > b:
        return
    if a == b:
        ans = cnt + 1
        return
    else:
        cal(a * 2, b, cnt + 1)
        cal((a * 10) + 1, b, cnt + 1)


A, B = map(int, input().split())
ans = -1
cal(A, B, 0)
print(ans)

알게된 것👨‍💻

• 재귀재귀재귀재귀