[백준] 2618: 경찰차

0. 문제 주소

 

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

2618번: 경찰차

 

 

1. 풀이

 

 

메모이제이션 없이 풀려면 2^1000가지 경우를 다 봐야 한다.

 

사건이 W개 있을 때, 0번째 사건이 (1, 1), 1번째 사건이 (N, N)에서 일어났다고 하고,

 

2번째 ~ W+1번째 사건의 좌표를 저장해둔다.

 

다음 dp 테이블의 정의를 아래와 같이 한다.

 

dp[i][j] = 경찰차1이 i번째 사건, 경찰차2가 j번째 사건을 해결한 상황일 때, 앞으로의 이동거리 중 최솟값

 

다음 solve 함수를 아래와 같이 설계한다.

 

int solve(int a, int b){
    int curr_num = max(a, b) + 1;
    if (curr_num == W+2) return 0;
    
    int &ret = dp[a][b];
    if (ret != -1) return ret;
    
    int X = solve(curr_num, b) + dist(task[a], task[curr_num]);
    int Y = solve(a, curr_num) + dist(task[b], task[curr_num]);
    if (X < Y) ans[a][b] = 1;
    else ans[a][b] = 2;
    
    return ret = min(X, Y);
}

 

현재 경찰차 1이 a번, 경찰차 2가 b번 사건을 해결했다면, 다음에 해결해야 할 사건의 번호는

 

curr_num = max(a, b) + 1이 된다.

 

경찰차 1과 경찰차 2 각각을 curr_num번 사건을 해결하게 하고. 둘 중 더 작은 값을 dp[a][b]에 저장해준다.

 

추가적으로 트래킹을 위해 "ans[a][b] = 각각 a, b번 사건을 처리한 상황일 때, 다음 사건을 처리할 번호"를 저장해준다.

 

 

맨 처음엔 ans 배열을 1차원으로 짜고 curr_num번째 사건을 처리할 경찰 번호를 저장해줬는데

 

이 경우 각각의 경우마다 매번 ans[curr_num]이 갱신되어서 최적의 해를 저장하지 못하는 문제가 생긴다.

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

#define pii pair<int, int>
#define MAX 1005

using namespace std;

int N, W;
pii task[MAX];
int dp[MAX][MAX];
int ans[MAX][MAX];

int dist(pii A, pii B){
    return abs(A.first - B.first) + abs(A.second - B.second);
}

int solve(int a, int b){
    int curr_num = max(a, b) + 1;
    if (curr_num == W+2) return 0;
    
    int &ret = dp[a][b];
    if (ret != -1) return ret;
    
    int X = solve(curr_num, b) + dist(task[a], task[curr_num]);
    int Y = solve(a, curr_num) + dist(task[b], task[curr_num]);
    if (X < Y) ans[a][b] = 1;
    else ans[a][b] = 2;
    
    return ret = min(X, Y);
}

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif
    
    scanf("%d %d", &N, &W);
    
    memset(dp, -1, sizeof(dp));
    
    task[0] = pii(1, 1);
    task[1] = pii(N, N);
    int x, y;
    for (int i=2;i<=W+1;i++){
        scanf("%d %d", &x, &y);
        task[i] = pii(x, y);
    }
    
    printf("%d\n", solve(0, 1));
    
    for (int x=0, y=1; max(x, y)+1 <= W+1; ){
        printf("%d\n", ans[x][y]);
        if (ans[x][y] == 1) x = max(x,y) + 1;
        else y = max(x, y) + 1;
    }
    
    return 0;
}