[DP(Top-Down)] 백준 2618 경찰차 C++

 

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

2618번: 경찰차

#include<iostream>
#include<vector>
#include<algorithm>
#define MAX 1001
using namespace std;

int n, w, a, b;
int dp[MAX][MAX];
vector<pair<int, int>> v1;
vector<pair<int, int>> v2;
vector<int> t;

void calDp(int x, int y) {
    if ((x == w) || (y == w)) return;
    if (dp[x][y] != 0) return; // 한 번 계산한 것 다시 계산X
    
    int num = max(x, y) + 1;
    int dist1, dist2;

    dist1 = abs(v1[x].first - v1[num].first) + abs(v1[x].second - v1[num].second);
    dist2 = abs(v2[num].first - v2[y].first) + abs(v2[num].second - v2[y].second); // 함수 새로X

    calDp(num, y);
    calDp(x, num);
    
    dp[x][y] = min(dp[num][y] + dist1, dp[x][num] + dist2);
}

void tracking(int x, int y)
{
    if ((x == w) || (y == w)) return;

    int num = max(x, y) + 1;
    int dist1, dist2;

    dist1 = abs(v1[x].first - v1[num].first) + abs(v1[x].second - v1[num].second);
    dist2 = abs(v2[num].first - v2[y].first) + abs(v2[num].second - v2[y].second); // 함수 새로X

    if (dp[num][y] + dist1 > dp[x][num] + dist2) { // 작은 것 선택
        t.push_back(2);
        tracking(x, num);
    }
    else {
        t.push_back(1);
        tracking(num, y);
    }
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0), cout.tie(0);
    cin >> n >> w;

    v1.push_back({ 0,0 });
    v2.push_back({ n - 1,n - 1 });
    for (int i = 0; i < w; i++) {
        cin >> a >> b;
        a--;  // 인덱스
        b--;
        v1.push_back({ a,b });
        v2.push_back({ a,b });
    }
    
    calDp(0, 0);  // 시작 0, 0
    tracking(0, 0);

    cout << dp[0][0] << "\n";
    for (int i = 0; i < t.size(); i++) cout << t[i] << "\n";
}