[Baekjoon] Graph - 16953 A → B

문제

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

 

풀이

A를 B로 바꾸는 조건

1. 2를 곱한다.

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

 

A(작은 수)를 B(큰 수)로 변경하려면 많은 고려사항이 필요하다. (2를 곱해보고 1을 추가하고, 2를 여러번 곱하고 1을 추가하고 등)

반대로 생각하여 B를 A로 변경할 수 있는지 확인하면 된다.

 

1. 2를 나눈다.

2. 1을 수의 가장 오른쪽에거 제거한다.

3. 1을 제외한 홀수인 경우 만들 수 없다.

 

예시

1) 2, 162 가 주어진 경우

 

162: 짝수이므로 2로 나눈다.

81: 1을 가지므로 오른쪽에서 제거한다.

8: 짝수이므로 2로 나눈다.

4: 짝수이므로 2로 나눈다.

2: A와 동일하므로 종료한다.

 

2) 4, 42 가 주어진 경우

42: 짝수이므로 2로 나눈다.

21: 1을 가지므로 오른쪽에서 제거한다.

2: A보다 작으므로 종료한다. (-1 출력)

 

3) 2, 21 이 주어진 경우

21: 1을 가지므로 오른쪽에서 제거한다.

2: A와 동일하므로 종료한다.

 

코드

import sys

a, b = map(int, sys.stdin.readline().rstrip().split())
# 연산의 최솟값에 1을 더해야하므로 미리 추가
result = 1

while a < b:
    # 1을 가지는 경우 1 제거
    if b % 10 == 1:
        b //= 10
        result += 1
        continue

    # 짝수인 경우 2로 나누기
    if b % 2 == 0:
        b //= 2
        result += 1
        continue

    # 1이 아닌 홀수인 경우 만들 수 없음
    if b % 10 != 1:
        result = -1
        break

print(-1 if a > b else result)