백준 2618 - 경찰차 (C++)

문제 문제 링크 BOJ 2618 - 경찰차 문제 요약 $2$차원 맵에서 $w$개의 사건이 발생한다. 두 대의 경찰차가 사건을 순차적으로 해결할 때, 두 대의 경찰차가 이동하는 거리의 합을 최소로 하는 경로를 찾아보자.

제한 TL : $1$ sec, ML : $128$ MB $5 ≤ N ≤ 1,000$ $1 ≤ W ≤ 1,000$ 알고리즘 분류 다이나믹 프로그래밍(dp) 풀이 플래티넘 $dp$계의 수문장같은 바이블 문제이다. 결국 매 시점마다 변하는 상태는 경찰차들의 위치 뿐이다.

이에 따라 다음과 같이 정의를 내려보자. $dp[p][q]$ : 각 경찰차의 마지막으로 해결한 사건 번호가 각각 $p, q$일 때 이동하는 거리 합의 최솟값.

이런 문제는 사실 위처럼 점화식 정의를 내리기까지가 문제이지 막상 정.....