BaekJoon16953_A->B

문제

풀이

이 문제는 두가지 풀이법이 있다. top-down 방식으로 b를 a로 만들어가는 방식과 bottom-up 방식으로 a를 b로 만드는 bfs방식이 있다.
문제에서 a를 b로 만들어가는 방식에는 x2 연산과 끝자리에 1을 붙여가는 방식이 있다. 즉, b가 짝수이거나 끝자리가 1인 경우만 a를 통해 만들 수 있다. top-down 방식으로 푸는 경우는 이런 과정을 통해 수행된다.

bottom-up 방식의 bfs 방식은 연산의 수행과정을 큐에 계속 넣어가면서 답을 찾는 과정을 수행한다.

풀이 코드

top-down 방식

import sys
input = sys.stdin.readline

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

cnt = 1

while b != a:
    cnt += 1
    temp = b
    if b % 10 == 1:
        b //= 10
    elif b % 2 == 0:
        b //= 2
        
    if temp == b:
        print(-1)
        break

else:
    print(cnt)

bfs를 이용한 방식

import sys
from collections import deque
input = sys.stdin.readline

a, b = map(int,input().split())
q = deque()
q.append((a,1))
r = 0

while(q):
    n,t = q.popleft()
    
    if n > b:
        continue
    if n == b:
        print(t)
        break
    
    q.append((int(str(n)+"1"), t+1))
    q.append((n*2, t+1))
    
else:
    print(-1)