이번 문제는 다익스트라 알고리즘을 사용하여 해결하였다. 탐색의 범위를 n과 k 중 더 큰 수의 2배까지로 설정하였고, 이동 방향을 dx는 [0, -1, 1]로, tp는 [2, 1, 1]로 설정하였다. 다음 탐색 인덱스는 (cur+dx[i])*tp[i]가 된다. 즉 dx[0], tp[0]은 순간이동에 해당하고, 나머지 경우는 걷는 것에 해당한다. 그러므로 순간이동인 i=0의 경우에만 비용을 추가하지 않고, 걷는 경우에는 비용을 추가해주는 방식으로 구현하였다. 탐색의 조건은 탐색의 범위 내에 있을 동안이다. 다익스트라 안에서 위와 같은 과정을 거치며 각 인덱스마다의 최소 비용을 저장한 후, k에 해당하는 최소 비용을 출력하도록 한다.

• n, k를 입력받는다.
• dx를 [0, -1, 1]로 선언한다.
• tp를 [2, 1, 1]로 선언한다.
• INF를 sys.maxsize로 선언한다.
• mx를 max(k, n)*2+1로 선언한다.
• 최소 비용을 저장할 리스트 dist를 INF mx개로 채운다.
• dist[n]을 0으로 갱신한다.
• 다익스트라에 사용할 q를 최소힙으로 선언하고, (0, n)을 넣는다.
• q가 존재할 동안 반복하는 while문을 돌린다.
  -> cost, cur을 q에서 추출한다.
  -> 만약 dist[cur]이 cost보다 작을 경우, 다음 반복으로 넘어간다.
  -> 3번 반복하는 i에 대한 for문을 돌린다.
  --> 다음 인덱스에 해당하는 nx를 (cur+dx[i])*tp[i]로 저장한다.
  --> 만약 nx가 0보다 크거나 같고, mx보다 작을 경우,
  ---> n_cost를 cost로 저장한다.
  ---> 만약 i가 0이 아닐 경우, n_cost를 1 증가시킨다.
  ---> n_cost가 dist[nx]보다 작을 경우,
  ----> dist[nx]를 n_cost로 갱신한다.
  ----> q에 (n_cost, nx)를 넣는다.
• dist[k]를 출력한다.

Code

import sys
import heapq
n, k=map(int, input().split())
dx=[0, -1, 1]
tp=[2, 1, 1]
INF=sys.maxsize
mx=max(k, n)*2+1
dist=[INF for _ in range(mx)]
dist[n]=0
q=[]
heapq.heappush(q, (0, n))
while q:
    cost, cur=heapq.heappop(q)
    if dist[cur]<cost:
        continue
    for i in range(3):
        nx=(cur+dx[i])*tp[i]
        if 0<=nx<mx:
            n_cost=cost
            if i!=0:
                n_cost+=1
            if n_cost<dist[nx]:
                dist[nx]=n_cost
                heapq.heappush(q, (n_cost, nx))
print(dist[k])