[BOJ 2618] 경찰차

문제

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

2618번: 경찰차

 

---

알고리즘

• DP

---

풀이

점화식을 세우는 것이 조금 어려웠습니다. 하지만 점화식만 잘 세우면 구현과 역추적은 쉽습니다.

 

배열 \(2\)개를 만들어 다음과 같이 정의합니다;

 

• \(dp[i][j]:\) 두 경찰차가 마지막으로 처리한 사건이 각각 \(i, j\)일 때(두 경찰차의 위치가 각각 사건 \(i\), 사건 \(j\)의 위치일 때), 마지막으로 처리된 사건의 다음 사건부터 마지막 사건을 해결하기 위해 두 경찰차가 이동해야하는 거리의 최솟값.
• \(track[i][j]:\) \(i, j\)의 정의가 위와 같을 때, 다음 사건을 처리해야하는 경찰차의 번호. (여기서는 \(1\)과 \(0\)으로 표현)

\(dp[i][j]\)일 때는 마지막으로 처리된 사건이 \(\max(i, j)\)가 됩니다. 그러므로, 다음 사건은 \(\max(i, j) + 1\)이 됩니다.

\(track[i][j]\)는 \(dp[i][j]\)에서 구해보고 더 작은값에 따라 다음 경찰차의 번호를 선택하면 됩니다.

그러므로, \(dist(i, j)\)를 \(i\)번째 사건의 지점에서 \(j\)번째 사건의 지점까지의 거리라고 하고 \(next = max(i, j) + 1\)이라고 할 때, 점화식을 다음과 같이 세울 수 있습니다:

$$dp[i][j] = \min \begin{cases}
dp[next + 1][j] + dist(i, next)\\
dp[i][next + 1] + dist(j, next)
\end{cases}$$

$$track[i][j] = \begin{cases}
1, & \text{if}\ dp[next + 1][j] + dist(i, next) < dp[i][next + 1] + dist(j, next)\\ 
0, & \text{otherwise}\
\end{cases}$$

최소 거리를 구한 후, \(track[i][j]\)를 이용하여 역추적하면 사건을 처리한 경찰차 번호를 알 수 있습니다.

 

시간복잡도: \(O(W^2)\)

 

---

코드

#include <bits/stdc++.h>
#define x first
#define y second
#define pb push_back
#define all(x) (x).begin(), (x).end()
#define rall(x) (x).rbegin(), (x).rend()
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

int N, W, dp[1001][1001];
bool track[1001][1001];
pii evt[1001];

int dfs(int i, int j, int k) {
    if (i >= W || j >= W) return dp[i][j] = k;
    if (dp[i][j]) return dp[i][j] + k;

    pii cur_i = evt[i], cur_j = evt[j];
    if (!i) cur_i = {1, 1};
    if (!j) cur_j = {N, N};
    
    int next = max(i, j) + 1;
    int next_i = abs(cur_i.x - evt[next].x) + abs(cur_i.y - evt[next].y);
    int next_j = abs(cur_j.x - evt[next].x) + abs(cur_j.y - evt[next].y);

    int a = dfs(next, j, k + next_i);
    int b = dfs(i, next, k + next_j);

    dp[i][j] = min(a, b) - k;
    track[i][j] = a < b;

    return dp[i][j] + k;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> N >> W;
    for (int i = 1; i <= W; ++i) cin >> evt[i].x >> evt[i].y;
    cout << dfs(0, 0, 0) << '\n';

    int i = 0, j = 0;
    while (i < W && j < W) {
        int next = max(i, j) + 1;
        if (track[i][j])
            i = next;
        else
            j = next;
        cout << (i < j) + 1 << '\n';
    }

    return 0;
}