[백준] 16953번 A → B (python)

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

16953번: A → B

 

1. A에 2를 곱하기

2. A의 가장 오른쪽에 1을 추가하기

위 두 가지 방식만 써서 A를 B로 만드는 문제이다. 하지만 나는 B를 A로 만들어서 연산의 최솟값을 구했다.

 

B에서 A를 만들어야겠다고 생각한 가장 큰 이유는, A의 가장 오른쪽에 1을 추가하는 시기를 결정하기 어렵기 때문이다. B를 2로 나누면서 가다 보면 일의 자리 수가 1인 경우가 발생하고, 이때 1을 삭제해 주면 같은 로직으로 구현된다. 이 방법을 통해 B에서 A를 찾아나갔고, 해당 연산의 최솟값을 구했다.

 

 

소스 코드

import sys
input = sys.stdin.readline

A, B = map(int, input().split())

count = 1
while True:
    if A > B:
        print(-1)
        break

    if A == B:
        print(count)
        break

    if B % 2 == 0: # 짝수
        B = B // 2

    elif str(B)[-1] == "1":
        B = int(str(B)[:-1])

    else:
        print(-1)
        break
    
    count += 1