[BOJ] A -> B

---

코드

import sys
input = sys.stdin.readline

a, b = map(int, input().split())

ans = 0
flag = False
while b >= a:
    if b == a:
        flag = True
        ans += 1
        print(ans)
        break
        
    nl = list(str(b))
    end = nl[-1]    
    
    if b % 2 == 0:
        b //= 2
    elif end == '1':
        nl.pop(-1)
        b = int(''.join(nl))
    else:
        break

    ans += 1

if not flag:
    print(-1)

결과

풀이 방법

• B가 짝수이면 2를 나누고, 끝자리가 1이면 끝자리 1을 제거하는 과정을 반복하다가 이 외의 경우에는 A로부터 만들어질 수 없으므로 -1을 출력하고 도중에 A가 만들어지면 반복횟수를 출력한다.
• 위의 그리디 방법 대신 BFS를 활용하여 문제를 풀 수도 있다. A로부터 곱하기 2, 끝자리 1 추가 연산을 수행하고 큐에 삽입하면서 큐에서 꺼낸 수가 B와 같아지면 카운트를 출력하는 방식이다.

---