Hello, Freakin world!

www.acmicpc.net/problem/13549 13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 �� www.acmicpc.net 다익스트라 알고리즘으로 풀기 전에 DP로 풀 수 있지 않을까? 라고 생각했지만 어렵겠다고 결론을 내렸습니다. 이유는 수빈이가 x-1로도 움직일 수 있기 때문입니다. 점화식은 구해지지만 이 경우 재귀로 풀어야 하는데 시간복잡도가 O(3^n)이 되므로 불가능합니다. 전형적인 다익스트라 알고리즘에 약간 추가로 생각해줘야 할 점이 있습니다. 그래프 노드의 범위를 정해주는 겁니다...