16953. A → B

문제가 궁금하시다면 아래의 링크를 눌러주세요!
문제 본문

접근 과정

• 작은 수에서 2를 곱하거나, 1을 더해가는 것보다는 큰 수에서 1을 떼어내거나, 2로 나누는 것이 더 빠르지 않을까?
• 2로 나누어가면서 끝자리가 1이 되는 경우 1을 제거한다.
• 만약 2로 나누어 떨어지지 않는 경우 정수 A로 만들 수 없는 수로 판단해 -1을 출력한다.
  
  
• 시간 제한은 2초! 값은 10억까지 들어올 수 있다.
• O(log n)정도의 복잡도로 해결할 수 있지 않을까?

풀이

import sys
A, B = map(int, sys.stdin.readline().split())
cnt = 0

while B != A:                       # B가 A와 같아지거나, 혹은 조건을 만족시키지 못하게 된다면 탈출한다.
    if cnt == -1:                   # 탈출
        break

    if str(B)[-1] == '1':           # 마지막 숫자가 1인 경우
        B //= 10                    # 1을 제거해주어야 하는데, 문자열로 처리해서 슬라이싱할 수도 있지만
        cnt += 1                    # 1의 자리를 없애는 것이기에 10으로 나눈 몫으로 처리할 수도 있다.
        continue

    if B > 0 and B % 2 == 0:        # 0보다 크면서 2로 나누어떨어지는 경우 2로 나누어준다.
        B //= 2                     # 0보다 크다라는 조건을 넣은 이유는 B가 1이 될 때 B > 0 조건이 없다면
        cnt += 1                    # 위의 조건문에서 1이 없어지게 되고, 0이 되어서 B % 2 == 0의 조건에서 무한루프가 생긴다.
        continue

    cnt = -1

print(cnt + 1) if cnt > 0 else print(-1)    # 불필요하게 쓴 것 같다. 처음부터 cnt에 1을 할당했다면 이렇게까진 하지 않아도 됬을텐데..

읽어주셔서 감사합니다!