[Algorithm] BAEKJOON 16953번: A → B (Python)

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

 

 

 

 

문제

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

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

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

 

입력

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

 

출력

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

 

 

 

 

 

풀이

그리디 알고리즘을 사용해서 B에서 A로 변환하는 과정에서 각 단계에서 가능한 두 가지 연산 중 최적의 연산을 선택하여 해결하였다.

 

 

Python 소스 코드

def min_operations(A, B):
    operations = 0

    while B > A:
        if B % 10 == 1:
            B //= 10
        elif B % 2 == 0:
            B //= 2
        else:
            break
        operations += 1

    if B == A:
        return operations + 1
    else:
        return -1


# 입력 받기
A, B = map(int, input().split())

# 결과 출력
print(min_operations(A, B))