BOJ 백준 2184번 김치배달

BOJ 백준 2184 김치배달

문제: www.acmicpc.net/problem/2184

2184번: 김치 배달

​

김치 N 개를 N 개의 도시들에 배달하는데, 김치 공장과 각각의 도시들은 1차원 직선상의 점에 위치해 있다. 이 좌표계의 좌표 값은 정수임을 전제로 한다.

 

김치를 각 도시에 배달하면서 1차원 직선을 따라 1초에 한 칸씩 움직일 수 있고, 김치는 1초에 1만큼씩 쉬게 된다. 그리고 각 도시에 도착하는 그 순간 김치가 배달되는 것으로 가정한다. 즉, 어떤 도시에 도착하는 순간 해당 도시로 김치 배달이 완료된다. 각 도시에 김치가 도착했을 때의 김치의 쉰 정도의 합의 최솟값을 구하는 것이 이 문제의 목표이다.

 

 

 

김치 공장 위치를 기준으로 양옆을 왔다 갔다 하며 또는 한쪽 방향으로만 계속 이동하는 특징을 보이는데, 이러한 문제는 Dynamic programming으로 해결할 수 있다. 그리고 이 문제처럼 1차원 좌표계를 좌우로 움직이면서 주어진 모든 좌표나 위치에 도달했을 때 구할 수 있는 value의 최솟값 또는 최댓값을 구하는 문제 유형은 종종 보인다. 주목해야 할 점은 어느 한 지점 A에서 다른 지점 B로 이동할 때 A와 B 사이에 있는 지점들은 모두 방문을 한 것으로 처리해야 최솟값을 얻을 수 있다. 그러므로 김치 배달원이 배달한 도시들은 항상 연속적인 범위를 갖는다.

 

​

 

dp[left][right][where]: left부터 right까지 이 범위에 있는 도시들에 배달한 상태에서, 현재 배달원이 where에 있을 때 김치 쉰 정도 합의 최솟값

where: 현재 배달원이 left에 있는지 (where 값이 0인 경우), right에 있는지 (where 값이 1인 경우)

 

 

​

각 도시에 배달할 때마다 아직 배달을 완료하지 않은 남은 도시들로 배달해야 하는 김치들의 쉰 정도가 각각 누적되기 때문에 남은 도시들의 개수도 고려해 줘야 한다. 그러나 이는 이제까지 배달을 완료한 도시 범위만 알면 남은 도시들은 자연적으로 구할 수 있으므로 이를 또 다른 상태로 기억해야 할 필요는 없다.

 

 

​

num(남은 도시의 개수): (n + 1) - (right - left + 1)

 

 

 

코드 구현이 좀 더 수월하도록 공장도 방문하는 도시의 일부로 포함하기로 전제했다.

 

 

 

1) 배달원이 현재 배달 완료한 도시 범위에서 가장 왼쪽에 위치할 때

 

(1) 현재 있는 도시에서 바로 왼쪽에 있는 도시로 이동

 

dp[left][right][0] = dp[left - 1][right][0] + num * (pos[left] - pos[left - 1])

 

 

(2) 배달 완료한 가장 오른쪽의 도시에서 바로 오른쪽에 있는 도시로 이동

 

dp[left][right][0] = dp[left][right + 1][1] + num * (pos[right + 1] - pos[left])

 

 

 

2) 배달원이 현재 배달 완료한 도시 범위에서 가장 오른쪽에 위치할 때

 

(1) 현재 있는 도시에서 바로 오른쪽에 있는 도시로 이동

 

dp[left][right][1] = dp[left][right + 1][1] + num * (pos[right + 1] - pos[right])

 

 

(2) 배달 완료한 가장 왼쪽의 도시에서 바로 왼쪽에 있는 도시로 이동

 

dp[left][right][1] = dp[left - 1][right][0] + num * (pos[right] - pos[left - 1])

 

 

 

#include <cstdio>
#include <vector>
#include <cstring>
#include <algorithm>
using namespace std;

const int N_MAX = 1000;
const int INF = 0x3f3f3f3f;

int n, l;
vector<int> pos, sum;
int dp[N_MAX + 1][N_MAX + 1][2];

int go(int left, int right, int where){
    if (left == 0 && right == n) {
        return 0;
    }
    
    int& ret = dp[left][right][where];
    if (ret != -1){
        return ret;
    }
    ret = INF;
    
    if (where == 0){
        if (left - 1 >= 0){
            ret = min(ret, go(left - 1, right, 0) + (pos[left] - pos[left - 1]) * (n + 1 - (right - left + 1)));
        }
        if (right + 1 <= n){
            ret = min(ret, go(left, right + 1, 1) + (pos[right + 1] - pos[left]) * (n + 1 - (right - left + 1)));
        }
    }
    else {
        if (left - 1 >= 0) {
            ret = min(ret, go(left - 1, right, 0) + (pos[right] - pos[left - 1]) * (n + 1 - (right - left + 1)));
        }
        if (right + 1 <= n){
            ret = min(ret, go(left, right + 1, 1) + (pos[right + 1] - pos[right]) * (n + 1 - (right - left + 1)));
        }
    }
    
    return ret;
}

int main(){
    scanf("%d %d", &n, &l);
    
    memset(dp, -1, sizeof(dp));
    
    pos.push_back(l);
    for (int i = 0; i < n; i++){
        int x; scanf("%d", &x);
        pos.push_back(x);
    }
    
    sort(pos.begin(), pos.end());
    
    int start = 0;
    for (int i = 0; i <= n; i++){
        if (pos[i] == l){
            start = i;
        }
    }
    
    printf("%d\n", go(start, start, 0));
    
    return 0;
}