HwangHub

13549번: 숨바꼭질 3 수빈이는 동생과 숨바꼭질을 하고 있다. 수빈이는 현재 점 N(0 ≤ N ≤ 100,000)에 있고, 동생은 점 K(0 ≤ K ≤ 100,000)에 있다. 수빈이는 걷거나 순간이동을 할 수 있다. 만약, 수빈이의 위치가 X일 때 www.acmicpc.net 🤔 Intuition 처음에는 DP라고 생각했다. 근데 아니였다. DP가 성립하려면 2가지 조건을 성립해야 한다. 부분 반복 문제 (Overlapping subproblem) : 어떤 문제가 부분 문제로 쪼개질 수 있는지 최적 부분 구조 (optimal substructure) : 부분 문제에서 구한 최적의 답이, 원래 문제의 최적의 답과 동일한지 이 문제를 통해 위 조건을 검토해보자면, 부분 반복은 된다. 왼쪽으로 한칸, 오..