경찰차

백준 2618번: 경찰차

아이디어

1번 경찰차, 2번 경찰차가 현재 맡은 사건 번호로 메모이제이션. 이 때 처음에는 (1, 1), (N, N)에서 시작하니 그 부분만 따로 계산해주면 된다.

tracking은 메모이제이션한 값 비교를 통해 몇번 경찰차가 사건을 맡았는지 구할 수 있다.
cache[p1][p2] - cache[next][p2] == dist(p1, next)인 경우 1번 차량이 next번 사건을 맡은 것이다.
tracking중 값 비교를 위해 next == W+1인 경우도 cache[p1][p2]를 0으로 설정하고 종료한다.

코드

#include <bits/stdc++.h>

using namespace std;

int N, W, cache[1001][1001];
vector<pair<int ,int>> v;

int get_dist(int cur, int next, int p) {
    int cx = v[cur].first;
    int cy = v[cur].second;
    if (!cur) {
        if (p == 1) {
            cx = 1;
            cy = 1;
        }
        else if (p == 2) {
            cx = N;
            cy = N;
        }
    }
    return abs(v[next].first-cx) + abs(v[next].second-cy);
}

int solve(int p1, int p2, int next) {
    int& ret = cache[p1][p2];
    if (ret != -1) return ret;

    if (next == W+1) return ret = 0;

    int r1 = solve(next, p2, next+1) + get_dist(p1, next, 1);
    int r2 = solve(p1, next, next+1) + get_dist(p2, next, 2);
    ret = min(r1, r2);

    return ret;
}

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

    cin >> N >> W;

    v = vector<pair<int, int>>(W+1);

    for (int i = 1; i < W+1; i++) {
        int a, b;
        cin >> a >> b;
        v[i] = {a, b};
    }

    memset(cache, -1, sizeof(cache));

    cout << solve(0, 0, 1) << '\n';

    vector<int> track;
    int p1 = 0, p2 = 0, next = 1;
    while (next != W+1) {
        if (cache[p1][p2] - cache[next][p2] == get_dist(p1, next, 1)) {
            track.push_back(1);
            p1 = next;
            next++;
        }
        else {
            track.push_back(2);
            p2 = next;
            next++;
        }
    }
    
    for (int x : track) {
        cout << x << '\n';
    }

    return 0;
}

여담

요즘 너무 놀았다. 다시 PS 열심히 해야겠다..