BOJ 2618 : 경찰차
BOJ 2618 : 경찰차 2618번: 경찰차 첫째 줄에는 동서방향 도로의 개수를 나타내는 정수 N(5≤N≤1,000)이 주어진다. 둘째 줄에는 처리해야 하는 사건의 개수를 나타내는 정수 W(1≤W≤1,000)가 주어진다. 셋째 줄부터 (W+2)번째 줄까지 www.acmicpc.net 아주 왤논 dp. 쫄고 있었는데 의외로 쉬워서 놀랐다. 환상의 듀엣 문제(먼저 보고 오는 걸 추천.)와 비슷한 느낌으로 dp를 해보자. dp[i][j] = i번째 사건을 1번 경찰차가, j번째 사건을 2번 경찰차가 담당할때 최적해. dist(i, j) = i번째 사건과 j번째 사건 사이의 유클리드 거리. nxt = 다음 사건. 이라고 정의한다면 dp[i][nxt] = min(dp[i][j] + dist(j, nxt), dp..
2021.04.30