[Python] BOJ / 16953번 / A → B

16953번: A → B

 

📝 문제

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

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

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

 

📜 풀이

• 탑다운(Top-down) 방식으로 생각하면 쉽게 구현할 수 있음
• 문제에 제시된 두 가지 연산 중에서 속도적으로 우위를 점할 수 있는 연산은 '1을 수의 가장 오른쪽에 추가한다'는 연산이므로 해당 연산을 우선적으로 수행하도록 해주어야 함
• 예를 들어, 40021이라는 숫자가 있을 때, 이는 4002에서 1을 추가함으로써 만들 수 있으며 이를 판단하는 방법은 10으로 나누었을 때 나머지가 1이라면 해당 연산을 수행할 수 있음
• 또한, 4002라는 숫자가 있을 때, 이는 2001에서 2를 곱함으로써 만들 수 있으며 이를 판단하는 방법은 2로 나누었을 때 나머지가 0이라면 해당 연산을 수행할 수 있음
• 만약 위 두 가지 경우에 속하지 않는다면, 문제에 제시된 두 가지 연산만으로는 A에서 B로 바꿀 수 없다는 것을 의미함

 

💻 소스코드

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

cnt = 0
while b > a:
    if b % 10 == 1:
        b //= 10
    elif b % 2 == 0:
        b //= 2
    else: break
    
    cnt += 1

print(cnt + 1 if a == b else -1)