[BOJ 2618] 경찰차

처음엔 DP를 정의하기 위해서, 5차원 배열(경찰차 1, 2의 위치 + 현재 해결중인 사건)을 생각했었는데,

 

 

 

1000^5는 메모리제한을 초과하게 된다.

 

 

 

5차원 배열의 크기를 줄이는 것을 생각해보면, 경찰차 1, 2이 해결한 마지막 사건들을 이용하면 된다. 왜냐하면, 같은 사건은 중복된 장소에서 발생하지 않으므로,

 

 

 

마지막 사건들은 즉, 현재 해결중인 사건을 표현하고 경찰차의 위치도 나타낼 수 있다.

 

 

 

전체 탐색을 통해서 DP 배열을 완성하고, 한 단계씩 최소값을 찾아가면서 값을 출력하면 된다.

 

 

 

해설코드(C++).

#include <iostream>
#include <vector>
#include <cstring>
 
using namespace std;
 
int N, W;
int dp[1001][1001];
vector<pair<int, int>> v;
 
int dis(int a, int b){
    int a_r = v[a].first;
    int a_c = v[a].second; 
    
    int b_r = v[b].first;
    int b_c = v[b].second;
    
    return abs(a_r - b_r) + abs(a_c - b_c);
}
 
int func(int w1, int w2){
    if(dp[w1][w2] != -1)
        return dp[w1][w2];
        
    if(w1 == W || w2 == W)
        return 0;
    
    dp[w1][w2] = 0;    
    int next = max(w1, w2) + 1;
    
    int val1 = 0;
    int val2 = 0;
    if(w1 == 0){
        val1 = func(next, w2) + abs(v[next].first - 1) + abs(v[next].second - 1);
        val2 = func(w1, next) + dis(w2, next);
    }else if(w2 == 0){
        val1 = func(next, w2) + dis(w1, next);
        val2 = func(w1, next) + abs(v[next].first - N) + abs(v[next].second - N);
    }else{
        val1 = func(next, w2) + dis(w1, next); 
        val2 = func(w1,next) + dis(w2, next);
    }
    
    dp[w1][w2] = min(val1, val2);
    return dp[w1][w2];
}
 
void print(int w1, int w2){
    if(w1 == W || w2 == W)
        return;
        
    int next = max(w1, w2) + 1;
    int val1, val2;
    
    if(w1 == 0 && w2 == 0){
        val1 = dp[next][w2] + abs(v[next].first - 1) + abs(v[next].second - 1);
        val2 = dp[w1][next] + abs(v[next].first - N) + abs(v[next].second - N);
    }
    else if(w1 == 0){
        val1 = dp[next][w2] + abs(v[next].first - 1) + abs(v[next].second - 1);
        val2 = dp[w1][next] + dis(w2, next);
    }else if(w2 == 0){
        val1 = dp[next][w2] + dis(w1, next);
        val2 = dp[w1][next] + abs(v[next].first - N) + abs(v[next].second - N);
    }else{
        val1 = dp[next][w2] + dis(w1, next); 
        val2 = dp[w1][next] + dis(w2, next);
    }
    
    if(val1 < val2){
        cout << 1 << endl;
        print(next, w2);
    }
    else{
        cout << 2 << endl;
        print(w1, next);
    }
    
    return;
}
 
int main() {
    cin >> N;
    cin >> W;
    v.push_back(make_pair(0, 0));
    
    int r, c;
    for(int i = 1; i <= W; i++){
        cin >> r >> c;
        v.push_back(make_pair(r, c));
    }
    
    memset(dp, -1 ,sizeof(dp));
    
    int result = min(func(1, 0) + abs(v[1].first - 1) + abs(v[1].second - 1), func(0, 1) + abs(N - v[1].first) + abs(N - v[1].second));
    cout << result << endl;
    print(0, 0);
 
    return 0;
}