[BaekJoon][2159] 케익 배달

BAEKJOON ONLINE JUDGE

2159 케익 배달

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

DP

입력 순서대로 좌표와 좌표 인접 지역을 가는 경우의 최소값을 각각 저장해 둔다.

dp table [n 번째 입력] [5(0 : 좌표, 1~4 : 좌표 인접지역)] = 거리 최소값

dp[n][i] = min(dp[n - 1][i] + [n - 1][i] 번째에서 [n][i]번째로의 거리)

#include <stdio.h>
#include <limits.h>
 
int n;
int beforex, beforey;
long long int dp[100001][5];
int dx[5] = { 0, 0, 0, -1, 1 };
int dy[5] = { 0, 1, -1, 0, 0 };
 
long long int abs(long long int n)
{
    if (n < 0)    return n * -1;
    return n;
}
 
int main()
{
    int i, j, k;
    int x, y;
    long long int min, temp;
 
    scanf("%d %d %d", &n, &beforex, &beforey);
 
    scanf("%d %d", &x, &y);
    for (i = 0; i < 5; i++) {
        min = LLONG_MAX;
        for (j = 0; j < 5; j++) {
            temp = abs(x + dx[i] - beforex) + abs(y + dy[i] - beforey);
            if (temp < min)    min = temp;
        }
        dp[1][i] = min;
    }
 
    beforex = x;
    beforey = y;
 
    for (i = 2; i <= n; i++) {
        scanf("%d %d", &x, &y);
 
        for (j = 0; j < 5; j++) {
            min = LLONG_MAX;
            for (k = 0; k < 5; k++) {
                temp = dp[i - 1][k] + abs(x + dx[j] - (beforex + dx[k])) 
                                + abs(y + dy[j] - (beforey + dy[k]));
                if (temp < min) {
                    min = temp;
                }
            }
            dp[i][j] = min;
        }
 
        beforex = x;
        beforey = y;
    }
 
    min = dp[n][0];
    for (i = 1; i < 5; i++) {
        if (dp[n][i] < min)    min = dp[n][i];
    }
 
    printf("%lld\n", min);
 
    return 0;
}