[BOJ][Python]16953번 풀이

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

16953번: A → B

from collections import deque

a,b = map(int, input().split())
q = deque([(a,0)])
ans = -1
while q:
    tmp = q.popleft()
    if tmp[0] == b:
        ans = tmp[1]+1
        break
    val1, val2 = tmp[0]*2, int(str(tmp[0])+'1')
    if val1 <= b:
        q.append((val1, tmp[1]+1))
    if val2 <= b:
        q.append((val2, tmp[1]+1))
print(ans)

아마 이 비슷한 문제를 풀었던 적이 있을겁니다. 클래스 몇이었는지는 잘 기억이 안나지만요(3이 bfs 천국이었으니 3아닐까 생각해봅니다). bfs에 대한 이해를 잘하고 있다면 어렵지 않은 문제입니다. 감소하는 경우도 없으니까요.

 

접근은 당연히 bfs입니다. 2를 곱하거나 맨 오른쪽에 1을 붙이거나해서 목표에 가장 빨리 도달한 횟수 + 1을 출력하는 문제인데, 사실 이쯤되면 대놓고 bfs 또는 그리디로 풀라고 말하는게 느껴지실겁니다. 보통 어떤 알고리즘으로 풀어라라는게 딱 보이는 순간 크게 어려운 부분들은 없어지는 것 같아요. 어떤 알고리즘을 사용하는게 최적인지 직감이 안올 때 많이 헤매게 되는 것 같습니다. 풀이 방법은 이젠 코드만 봐도 알 수 있으실 겁니다. 입력을 받아서 두 경우에 대해서 각각 목표보다 작거나 같은 경우에 queue에 추가해주면 끝이에요. 아예 불가능한 경우에 -1을 출력해야하니 미리 ans를 -1로 초기화하는 것만 주의합시다.