[Python] 백준/BOJ - 16953번: A -> B

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

16953번: A → B

문제

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

2를 곱한다.

1을 수의 가장 오른쪽에 추가한다.

 

입력

첫째 줄에 A, B(1 <= A <= B <= 10^9)

 

출력

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

 

예제 입력 1

2 1622

 

예제 출력 1

5

 

풀이

그리디 알고리즘을 이용해 풀었다. A -> B로 가는 것이 아닌 B를 A로 만드는 방식으로 해결했다.

 

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

cnt = 0

while True:
    cnt += 1
    
    if a > b or (b % 10 != 1 and b % 2 != 0):
        cnt = -1
        break
    elif b % 2 == 0:
        b /= 2
    elif b % 2 == 1:
        b //= 10

    if a == b:
        cnt += 1
        break

print(cnt)

 

B가 일의 자리수가 1이 아닌 홀수인 경우에는 바로 -1을 리턴하면 된다.

B의 일의자리수가 1일 경우에는 1을 뺀 값을 B에 저장해주면 되고, B가 짝수일 경우에는 2로 나눠준 값을 B에 저장해주면 된다.

이 과정에서 B가 A보다 작아진다면 이는 B를 A로 만들 수 없다는 의미이기 때문에 -1을 리턴해주면 된다.