백준 2618번 경찰차 (boj/2618.c)

DP문제입니다. 공간복잡도 O(W^2), 시간복잡도 O(W^2)으로 해결가능합니다.

또한 각 사건마다 할당된 경찰관을 묻고 있기 때문에 간단한 자취 남기기 기법을 응용합니다.

DP의 구성은 아래와 같습니다.

 

회색 영역은 초기화 때 계산됩니다.

빗금 영역에 있는 값 중 최소의 값을 문제의 답으로 결정합니다.

한 번에 계산되는 양은 아래와 같습니다.

코드는 아래와 같습니다.

#include <stdio.h>
#include <math.h>
#define SZE     1000
int dp[SZE+1][SZE+1];
int idx[SZE+1][2];
int giv[SZE+1] = { 0, };
typedef struct _p{
    int row;
    int col;
}point;
point loc[SZE+1];
int get_dst(point p1, point p2){
    return abs(p1.row-p2.row) + abs(p1.col-p2.col);
}
int main(void){
    int N, W;
    int row, col, tmp;
    int cur_row, cur_col, rec;
    int res;
    point pol1, pol2;
    scanf("%d %d", &N, &W);
    pol1.row=pol1.col=1; pol2.row=pol2.col=N;
    for(int i=1;i<=W;i++){
        scanf("%d %d", &row, &col);
        loc[i].row=row; loc[i].col=col;
    }
    //gray area (tmp = length loc1 to loci)
    tmp = 0;
    for(int i=1;i<=W;i++){
        if(i>1){ tmp += get_dst(loc[i-1], loc[i]); }
        dp[0][0] = 0;
        dp[i][0] = get_dst(pol1, loc[1]) + tmp;
        dp[0][i] = get_dst(pol2, loc[1]) + tmp;
    }
    for(int i=1;i<W;i++){
        //black area
        dp[i][i]=-1;
        //dark green area
        dp[i][i+1] = dp[i][0] + get_dst(pol2, loc[i+1]); idx[i][1] = 0;
        for(int j=1;j<i;j++){
            tmp = dp[i][j] + get_dst(loc[j], loc[i+1]);
            if(tmp < dp[i][i+1]){ dp[i][i+1] = tmp; idx[i][1]=j; }
        }
        //dark red area
        for(int j=i+2;j<=W;j++){ dp[i][j] = dp[i][j-1] + get_dst(loc[j-1], loc[j]); }
        //light green area
        dp[i+1][i] = dp[0][i] + get_dst(pol1, loc[i+1]); idx[i+1][0] = 0;
        for(int j=1;j<i;j++){
            tmp = dp[j][i] + get_dst(loc[j], loc[i+1]);
            if(tmp < dp[i+1][i]){ dp[i+1][i]=tmp; idx[i+1][0]=j; }
        }
        //light red area
        for(int j=i+2;j<=W;j++){ dp[j][i] = dp[j-1][i] + get_dst(loc[j-1], loc[j]); }
    }
    //search answer
    res = dp[0][W];
    for(int i=0;i<W;i++){
        if(res > dp[i][W]){ 
            res = dp[i][W];
            cur_row=i; cur_col=W; }
        if(res > dp[W][i]){ 
            res = dp[W][i];
            cur_row=W; cur_col=i; }
    }
    //make path
    rec=W;
    while(rec--){
        if(cur_row > cur_col+1){ 
            giv[rec] = 1; cur_row--; }
        else if(cur_row == cur_col+1){
            giv[rec] = 1; cur_row=idx[cur_row][0]; }
        else if(cur_row+1 == cur_col){
            giv[rec] = 2; cur_col=idx[cur_row][1]; }
        else if(cur_row+1 < cur_col){
            giv[rec] = 2; cur_col--; }
        else{ giv[rec]=-1; }
    }
    printf("%d\n", res);
    for(int i=0;i<W;i++){ printf("%d\n", giv[i]); }
    return 0;
}