BOJ 2618 : 경찰차
2021. 4. 30. 10:24ㆍPS/DP
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[i][nxt])
dp[nxt][j] = min(dp[i][j] + dist(i, nxt), dp[nxt][j])
역추적 때문에 탑다운으로 짰다.
djayy035/dj035_PS
코드저장소. Contribute to djayy035/dj035_PS development by creating an account on GitHub.
github.com
'PS > DP' 카테고리의 다른 글
| BOJ 1056 : 수 (2) | 2021.07.29 |
|---|---|
| BOJ 20984 : Growing Vegetables is Fun 4 (0) | 2021.05.11 |
| BOJ 11570 : 환상의 듀엣 (0) | 2021.04.30 |
| BOJ 14728 : 벼락치기 (0) | 2021.01.10 |
| BOJ 2688 : 줄어들지 않아 (0) | 2020.08.17 |