[c++] 백준 2618 - 경찰차(dp)

0. [c++] 백준

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

1. 풀이

2. 소스코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>
 
using namespace std;
 
const int INF = 1000000007;
int N, W;
vector<pair<int, int> > arr;
int cache[1001][1001];
int ans[1001];
 
int dp(const int final_order_A, const int final_order_B) {
    int here = max(final_order_A, final_order_B) + 1;
    if (here == arr.size())
        return 0;
    
    int & ret = cache[final_order_A][final_order_B];
    if (ret != 0)
        return ret;
 
    ret = INF;
 
    pair<int, int> a;
    pair<int, int> b;
    if (final_order_A == 0)
        a = { 1,1 };
    else
        a = arr[final_order_A];
    if (final_order_B == 0)
        b = { N,N };
    else
        b = arr[final_order_B];
 
    int a_ret = abs(a.first - arr[here].first) + abs(a.second - arr[here].second) + dp(here , final_order_B);
    int b_ret = abs(b.first - arr[here].first) + abs(b.second - arr[here].second) + dp(final_order_A, here);
    ret = min(a_ret, b_ret);
 
    return ret;
}
 
void find_order(int a, int b) {
    int here = max(a, b) + 1;
    if (here == arr.size())
        return;
    
    pair<int, int> c;
    pair<int, int> d;
    
    if (a == 0)
        c = { 1,1 };
    else
        c = arr[a];
    if (b == 0)
        d = { N,N };
    else
        d = arr[b];
 
    int a_ret = abs(c.first - arr[here].first) + abs(c.second - arr[here].second) + dp(here, b);
    int b_ret = abs(d.first - arr[here].first) + abs(d.second - arr[here].second) + dp(a, here);
 
    if (a_ret < b_ret) {
        ans[here] = 1;
        find_order(here, b);
    }
    else {
        ans[here] = 2;
        find_order(a, here);
    }
}
 
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
 
    cin >> N >> W;
    int a, b;
    arr.push_back({ 0,0 });
    for (int i = 0; i < W; i++) {
        cin >> a >> b;
        arr.push_back({ a,b });
    }
 
    cout << dp(0, 0) << endl;
    find_order(0, 0);
    for (int i = 1; i <= W; i++)
        cout << ans[i] << endl;
}

3. 참고

질문이나 지적 있으시면 댓글로 남겨주세요~

도움 되셨으면 하트 꾹!