테페리넷

이 문서는 읽기 전용입니다. 원본을 볼 수는 있지만 바꿀 수는 없습니다. 문제가 있다고 생각하면 관리자에게 문의하세요.
====== A → B ======

===== 풀이 =====
  * 현재 수에서 만들수 있는 다음 수가 2가지이므로, n번 연산으로 만들 수 있는 상태들을 큐에 저장해서 n+1번에 만들수 있는 수들을 찾는것을 반복하는 방법, 다시말하면 BFS를 사용해야 할 것 같다.
  * 하지만, 역으로 B에서 A로 변환시킨다고 생각하자. 역변환해서 사용할수 있는 연산은 2로 나누거나, 가장 오른쪽에 있는 1을 제거하는 것이다. 근데 2로 나누는 연산은 현재 수가 2의 배수일때만 가능하고, 1을 제거하는 것은 현재 수의 1의 자리가 1일때만 가능하다. 즉, 가능한 연산의 수는 최대 1개이고, 이러면 큐도 필요없이 단순 반복문으로 계산이 가능하다.
  * 구현할때는 B에서 시작해서 역변환을 적용하다가 값이 A와 같아지면 변환횟수를 출력한다. 가능한 변환이 없는 상태가 되거나, 변환한 값이 A보다 작아지면 -1을 출력하면 된다.
  * 변환 횟수만큼 루프를 돌게 되고, 변환을 한번 적용할때마다 크기가 절반이하로 줄어드므로 최대 변환 횟수는 log(B/A)이다. 따라서 시간복잡도는 O(logB)


===== 코드 =====
<dkpr py>
"""Solution code for "BOJ 16953. A → B".

- Problem link: https://www.acmicpc.net/problem/16953
- Solution link: http://www.teferi.net/ps/problems/boj/16953

Tags: [AdHoc]
"""


def main():
    A, B = [int(x) for x in input().split()]
    b = B
    count = 1
    while b > A:
        count += 1        
        if b % 2 == 0:
            b //= 2
        elif b % 10 == 1:
            b //= 10
        else:
            print('-1')
            break
    else:
        print(count if b == A else '-1')


if __name__ == '__main__':
    main()
</dkpr>

{{tag>BOJ ps:problems:boj:실버_1}}