백준 2618번 : 경찰차 - dp, C++

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

2618번: 경찰차

#include <bits/stdc++.h>

using namespace std;

const int MX = 1'000'001;
int N, W, dp[1003][1003];

vector<pair<int, int> > work;

int lastMax = MX;
pair<int, int> lastWork;

int getMaxDistance(int A, int B) {
    if (A == W || B == W) {
        return 0;
    }
    int &ret = dp[A][B];
    if (ret != -1) return ret;

    ret = MX;
    int nextWork = max(A, B) + 1;

    int ret1 = -1, ret2 = -1;
    //다음 일을 A가 할 때
    if (A == 0) {
        ret1 = getMaxDistance(nextWork, B) + abs(1 - work[nextWork].first) + abs(1 - work[nextWork].second);
    } else {
        ret1 = getMaxDistance(nextWork, B)
               + abs(work[A].first - work[nextWork].first) + abs(work[A].second - work[nextWork].second);
    }

    //다음 일을 B가 할 때
    if (B == 0) {
        ret2 = getMaxDistance(A, nextWork) + abs(N - work[nextWork].first) + abs(N - work[nextWork].second);
    } else
        ret2 = getMaxDistance(A, nextWork)
               + abs(work[B].first - work[nextWork].first) + abs(work[B].second - work[nextWork].second);

    return ret = min(ret1, ret2);
}


void reconstruct(int A, int B) {
    if (A == W || B == W) return;

    int nextWork = max(A, B) + 1;
    int ret1 = -1, ret2 = -1;
    //다음 일을 A가 할 때
    if (A == 0) {
        ret1 = dp[nextWork][B] + abs(1 - work[nextWork].first) + abs(1 - work[nextWork].second);
    } else {
        ret1 = dp[nextWork][B]
               + abs(work[A].first - work[nextWork].first) + abs(work[A].second - work[nextWork].second);
    }

    //다음 일을 B가 할 때
    if (B == 0) {
        ret2 = dp[A][nextWork] + abs(N - work[nextWork].first) + abs(N - work[nextWork].second);
    } else
        ret2 = dp[A][nextWork]
               + abs(work[B].first - work[nextWork].first) + abs(work[B].second - work[nextWork].second);

    if (ret1 < ret2) {
        cout << 1 << '\n';
        reconstruct(nextWork, B);
    } else {
        cout << 2 << '\n';
        reconstruct(A, nextWork);
    }
}


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

    cin >> N >> W;

    work.push_back({0, 0});
    for (int i = 0; i < W; i++) {
        int a, b;
        cin >> a >> b;
        work.push_back({a, b});
    }

    memset(dp, -1, sizeof(dp));
    cout << getMaxDistance(0, 0) << '\n';
    reconstruct(0, 0);

    return 0;
}