[코테] 백준 그리디 16953번 문제

16953번 : A → B

문제 링크

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

문제 설명

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

2를 곱한다. 1을 수의 가장 오른쪽에 추가한다. A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

입력

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

출력

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

문제 풀이

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

# a가 b보다 작을때까지 반복
while a < b : 
    # b의 1의 자리 숫자가 1이면 맨 끝 1을 뺀 값을 b에 저장
    if b % 10 == 1 : b = b // 10
        
    # b가 2의 배수이면 2로 나눈다
    elif b % 2 == 0 : b /= 2

    # 1을 제외한 홀수이면 더이상 값 처리가 불가하기에 반복문 나가기
    else : break
        
    # 연산 한 번마다 카운트 1개 추가
    count += 1

# a랑 b가 같으면 count, 아니면 -1 출력
if a == b : print(count)
else : print(-1)