[백준] 16953 A->B 파이썬 풀이

1. B를 A로 만들어보자!

나는 B->A로 만드는 방법을 떠올렸다

B에서 2로 나눠지면 나누고, B의 맨 마지막 숫자가 1이면 1을 떼어주고, 

2로 나눠지지 않고 마지막 숫자 (10으로 나눴을 때 나머지)가 1이 아니면 -1 을 리턴

+ 그런데 여기서, B는 항상 A보다 커야한다 ! 즉 B < A 인 값이 나와도 -1을 리턴한다

a, b = map(int, input().split())
count = 1
while True:
    if b == a:
        break
    elif (b % 2 != 0 and b%10 != 1) or (b < a):
        count = -1
        break
    else:
        if b%10 == 1:
            b //= 10
            count += 1
        else:
            b //= 2
            count += 1
        
print(count)

 

 

2. 사실 BFS로 푸는건 조금 생소했는데..! BFS로도 풀수있다 

from collections import deque
a, b = map(int, input().split())
result = -1
queue = deque()
queue.append((a, 1))
while queue:
    num, count = queue.popleft()
    if num == b:
        result = count
        break
    if num*2 <= b:
        queue.append((num*2, count+1))
    if int(str(num) +'1') <= b:
        queue.append((int(str(num)+'1'), count+1))
print(result)

 

queue에 (현재값, 계산한횟수)를 넣어준다. 

그리고 queue가 빌 때까지 연산한다.

현재 값을 요리조리 2배 하거나 뒤에 1붙여도 b보다 작거나 같으면 연산을 수행하고 , b랑 현재 값이 같아지면 연산 종료한다.

queue가 빌때까지 연산을 수행해도 b와 값이 같아지지 않으면 -1를 출력 ! 

재밌구만~