[BOJ #16953] A -> B

문제

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

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

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

 

입력

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

 

출력

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

 

내가 쓴 코드

import sys; input = sys.stdin.readline
A, B = map(int, input().split())
ans = 1
# 곱하기 2
# 수의 오른쪽에 1 추가
while B > A:
    if B % 10 == 1:
        ans += 1
        B //= 10
    elif B % 2 == 0:
        ans += 1
        B //= 2
    else:
        break

if A == B:
    print(ans)
else:
    print(-1)

while 문 안에 else: break 를 쓰지 않고 제출하니까 자꾸 시간 초과가 났다. while 문이라서 조건문에 만족할 때까지 반복하게 두면 시간 복잡도가 증가하는 것 같다. else: break 쓰니까 바로 해결 완료 !!

 

제출 결과