BOJ 2618 - 경찰차

BOJ 2618 - 경찰차

[분류 - 다이나믹 프로그래밍]

 

[풀이]

  경찰차 1이 있는 (1, 1)을 1번 사건, 경찰차 2가 있는 (N, N)을 2번 사건, 그리고 나머지 N개의 사건을 3, 4, ..., N+2번 사건이라고 하자. 각 경찰차가 마지막 사건을 처리한 위치가 각각 a, b라고 하면 그 다음 사건을 처리할 때 그 사건의 번호는 max(a, b) + 1이 된다(순차적으로 진행해야 하므로).

 

dp[a][b] = 경찰차 1이 a를 해결했고, 경찰차 2가 b를 해결했을 때 남은 모든 사건을 해결하기 위한 이동 최소

 

  이제 문제는 꽤 간단해진다.
  당연하게도 그 다음 사건 w(w = max(a, b) + 1)번 사건을 해결하기 위해서는 경찰차 1에 할당할 것인지 경찰차 2에 할당할 것인지 두 가지밖에 없다.

  dist(n1, n2)를 n1번 사건과 n2번 사건의 거리라고 정의할 때,
1. 경찰차 1에 할당하는 경우
  dp[w][b] + dist(a, w)를 부분 문제로 둘 수 있다.
2. 경찰차 2에 할당하는 경우
  dp[a][w] + dist(b, w)를 부분 문제로 둘 수 있다.

  위 경우를 모두 고려하고 최소값을 쫓아가도록 추적하는 로직을 짜주면 된다. 추적할 때 배열을 따로 둬서 저장해도 되고, 아니면 재귀를 통해 구현해도 된다.

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAX_W = 1002;
int N, W, pos[MAX_W][2], dp[MAX_W][MAX_W];
pair<int, int> trace[MAX_W][MAX_W];
int rec(int a, int b) {
    if (a == W || b == W) return 0;
    int& ret = dp[a][b];
    if (ret != -1) return ret;
    int w = max(a, b) + 1;
    ret = rec(w, b) + abs(pos[a][0] - pos[w][0]) + abs(pos[a][1] - pos[w][1]);
    trace[a][b] = { w, b };
    if (ret > rec(a, w) + abs(pos[b][0] - pos[w][0]) + abs(pos[b][1] - pos[w][1])) {
        ret = rec(a, w) + abs(pos[b][0] - pos[w][0]) + abs(pos[b][1] - pos[w][1]);
        trace[a][b] = { a, w };
    }
    return ret;
}
int main() {
    memset(dp, -1, sizeof dp);
    int i, a, b;
    scanf("%d%d", &N, &W);
    pos[0][0] = pos[0][1] = 1;
    pos[1][0] = pos[1][1] = N;
    W++;
    for (i = 2; i <= W; i++) scanf("%d%d", &pos[i][0], &pos[i][1]);
    printf("%d\n", rec(0, 1));
    for (a = 0, b = 1, i = 2; i <= W; i++) {
        auto nxt = trace[a][b];
        printf("%d\n", nxt.first == a ? 2 : 1);
        a = nxt.first, b = nxt.second;
    }
    return 0;
}