[BaekJoon][2184] 김치 배달

BAEKJOON ONLINE JUDGE

2184 김치 배달

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

DP

DP 테이블을 설정하기에 앞서

문제를 잘 파악하면 배달을 하기위한 움직임이 왼쪽으로 이동, 오른쪽으로 이동 밖에 없으며,

가는 길에 배달할 지역을 뛰어넘는 (예를 들어 10에서 출발, 9을 들리지 않고 1을 먼저 배달하는) 경우는 발생하지 않는다는 점을 알아야 한다.

따라서 DP 테이블을 구간으로 잡을 수 있는데 먼저, 

DP[left][right] 에서 left - right 범위 내 위치한 배달할 지역은 이미 배달을 완료한 상태로 최적화가 될 수 있다.

따라서 처음 공장 위치를 시작으로 범위를 점차 넓혀 나가는 식으로 탐색해 나간다.

또한 주의할 점이 하나 더 있다. 

예를 들어 10 - 9 - 11순으로 탐색 한 상태는 left : 1, right : 4이고, 10 - 11 - 9 순으로 배달을 마친 상태 left : 1, right : 4이다. DP 의 위치를 나타낼 값이 같지만 계산되어야 하는 값도 다르고, 마지막으로 배달을 마친 위치 또한 다르다. 따라서 이를 구분짓고, 마지막 위치를 나타낼 DP테이블이 추가되어야 한다.

[position]으로 DP테이블을 3차원으로 추가할 수 있지만, 마지막 위치가 구간이 되기도 하기 때문에 n개의 테이블을 추가로 잡는 것 보다 왼쪽 구간 위치인지 오른쪽 구간 위치인지를 구분할 flag만 있어도 충분하다.

따라서 DP[left][right][vector]        (n * n * 2)

#include <cstdio>
#include <algorithm>
using namespace std;
 
#define INF    987654321
#define Abs(n)            (((n) < 0)    ? ((n) * -1) : (n))
 
int n, l;
int input[1001];
int dp[1001][1001][2];
 
int go(int left, int right, int flag, int idx)
{
    int temp, current;
 
    if (left == 0 && right == n)        return 0;
    if (dp[left][right][flag])          return dp[left][right][flag];
    dp[left][right][flag] = INF;
 
    if (flag)   current = input[right];
    else        current = input[left];
 
    if (left > 0)     dp[left][right][flag] = go(left - 1, right, 0, idx - 1) 
                                              + idx * Abs(current - input[left - 1]);
    if (right < n) {
        temp = go(left, right + 1, 1, idx - 1) 
               + idx * Abs(current - input[right + 1]);
        if (temp < dp[left][right][flag])        dp[left][right][flag] = temp;
    }
 
    return dp[left][right][flag];
}
 
int main()
{
    int i;
 
    scanf("%d %d", &n, &l);
 
    input[0] = l;
 
    for (i = 1; i <= n; i++) {
        scanf("%d", &input[i]);
    }
 
    sort(input, input + n + 1);
 
    for (i = 0; input[i] != l; i++);
 
    printf("%d\n", go(i, i, 0, n));
 
    return 0;
}