[BOJ / 백준] 16953번 A → B 파이썬(Python) 문제 풀이

문제

 

문제 링크 : https://www.acmicpc.net/problem/16953

16953번: A → B

 

 

 

 

CODE

import sys
from collections import deque

input = sys.stdin.readline


def solve(a, b):
    q = deque([(a, 1)])

    while q:
        now, cnt = q.popleft()
        if now == b:
            print(cnt)
            return

        if now * 2 <= b:
            q.append((now * 2, cnt + 1))
        if now * 10 + 1 <= b:
            q.append((now * 10 + 1, cnt + 1))
    print(-1)


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

 

 

 

 

 

풀이

💡 idea

- BFS로 풀이!

- 쭉 풀어온 BFS 문제와 다른 부분이 없어 설명할 게 딱히 없네요,,,

 

💡 others

56ms 로 해결한 분의 풀이를 보면

m이 1로 끝날 때에는 10으로 나누고 2로 나누어 떨어질 땐 2로 나누는 식의 풀이를 하셨네요..!

n이 m보다 크거나 연산을 수행할 수 없을 때에는 count를 -2로 설정하여

후에 출력할 때 -1이 출력되도록 작성하셨습니다

훌륭한 코드 구경하고 가세요 🙇‍♀️

n,m = map(int,input().split())
count=0
while n!=m:
    if n>m:
        count=-2
        break
    elif str(m)[-1]=='1':
        m=m//10
        count+=1
    elif m%2==0:
        m=m//2
        count+=1
    else:
        count=-2
        break
print(count+1)

 

 

 

 

 

결과