[파이썬] 백준 알고리즘 No.16953 A -> B

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

16953번: A → B

 

"""
a - > b
1. 곱하기 2
2. 1을 수의 가장 오른쪽에 추가

"""
a, b = map(int, input().split())
count = 1

def go(a, b, count):
    if a == b:
        print(count)
        exit()
    if a > b:
        return
    go(a * 2, b, count + 1)
    go(int(str(a) + "1"), b, count + 1)


go(a, b, count)
print(-1)

 

재귀 함수를 이용하여 푼 문제

재귀의 조건을 살펴보자

1. A와 B가 같은 값이면 재귀 종료

2. A가 B보다 커지면 재귀 종료

3. 1-2에 해당하지 않는 경우 매 순간 a에 대해 곱하기 2, 1을 추가 해주면 됨