[코딩 테스트 연습(파이썬/Python)] 백준(BOJ) 16953번 _ A → B

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

16953번: A → B

[문제]

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

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

A를 B로 바꾸는데 필요한 연산의 최솟값을 구해보자.

 

[입력]

첫째 줄에 A, B (1 ≤ A < B ≤ 109)가 주어진다.

[출력]

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

 

[아이디어]

1) 거꾸로 B에서 출발해 A에 도달하는 시도를 하고, 실패하면 -1을 반환한다.

 

n,m = map(int, input().split())
cnt = 1
while True:
    cnt+=1
    if (m-1)%10==0:
        m = (m-1)//10
    elif m%2==0:
        m//=2
    if n==m:
        break
    elif ((m-1)%10 and m%2) or (m==0):
        cnt = -1
        break
print(cnt)

처음에 위와 같이 했는데, 어차피 m이 n보다 작아지면 종료되는 것이므로 아래처럼 바꾸어주면 좋을 것 같다.

n,m = map(int, input().split())
cnt = 1
while n<m:
    cnt+=1
    if (m-1)%10==0:
        m = (m-1)//10
    elif m%2==0:
        m//=2
    if ((m-1)%10 and m%2):
        break
print(cnt if n==m else -1)