[BOJ] 2618번: 경찰차

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

D[i][j]를 경찰차1의 최종 위치가 i, 경찰차2의 최종 위치가 j일 때 1~max(i, j) 사건까지 해결할 때의 이동 거리의 최솟값으로 둡니다. 사실 i나 j가 0이 아닐 경우(즉 경찰차 1,2 모두 출발했을 경우), D[i][j] = D[j][i]이긴 하지만 예외처리를 하는게 번거로워 그냥 공간을 2배 더 썼습니다.

일반성을 잃지 않고 i > j라고 할 때, j != i-1일 경우 D[i][j] = D[i-1][j] + dist(i-1,i)가 됩니다. 그리고 j = i-1일 경우 k = 0~i-2에 대해 D[i][j] = min(D[k][j]) + dist(k,i)가 됩니다.

D 테이블을 채운 뒤에 경로를 따라가는 것이 살짝 껄끄러웠는데, D 테이블의 값을 갱신할 때 마다 이 값이 어디서 왔는지를 기록해두어 해결했습니다. 이게 중등부 2번이라니 무시무시하네요.

https://github.com/blisstoner/BOJ/blob/master/2618.cpp