[baekjoon] 백준 16953번(파이썬): A → B

문제

16953번: A → B

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

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

- A를 B로 바꾸는데 필요한 연산의 최솟값을 구하는 문제이다.

-  A, B (1 ≤ A < B ≤ 109)가 주어진다.

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

- 만들 수 없는 경우에는 -1을 출력한다

알고리즘

- a, b를 입력받는다.

- 반복문을 통해 b를 a로 바꾼다.

- a와 b가 같거나 a가 b보다 커지는 경우 반복을 멈춰준다.

- a가 b보다 크다는 의미는 a로 b를 만들 수 없다는 것이다.

- b가 2로 나눠지면 b를 2로 나눈다.

- b를 10으로 나눴을 때 1이 남으면 b를 10으로 나눈 몫으로 초기화한다.

- 위 두 가지 경우가 아니라면 b로 a를 만들지 못하는 경우임으로 반복을 멈춘다.

코드

import sys

a, b = map(int, sys.stdin.readline().split())
# 처음 a 카운트
cnt = 1
# a와 b가 같거나 b로 a를 만들지 못하는 경우를 찾는다.
while True:
    # a와 b가 같으면 멈춘다.
    if a == b:
        break
    # a가 b보다 크면 b로 a를 만들지 못하는 경우임으로 멈춘다.
    elif a > b:
        cnt = -1
        break

    # b가 2로 나눠지면 b를 2로 나눈다.
    if b % 2 == 0:
        b //= 2
    # b를 10으로 나눴을 때 1이 남으면 b를 10으로 나눈 몫으로 초기화한다.
    elif b % 10 == 1:
        b = b // 10

    # 위 두가지 경우가 아니라면 b로 a를 만들지 못하는 경우임으로 멈춘다.
    else:
        cnt = -1
        break

    # 위 두가지 경우이면 카운트한다.
    cnt += 1

print(cnt)

github

junjange/CodingTest