[KOI] 백준 1866 - 택배

www.acmicpc.net/problem/1866

사전 지식

이 문제를 풀기 전에 USACO wifi setup과 BOJ 14400을 풀고 오는 것을 추천한다.

 

솔루션 - 편의점 2 / 솔루션 - wifi setup

풀이

트럭과 헬기를 적절히 써서 비용의 합을 최소로 해야한다.

 

비용의 최소는 wifi setup과 비슷하게 일차원 동적계획법으로 계산할 수 있다.

 

테이블의 정의는 dp[i] := i번째 지점까지 배송했을 때 비용의 최소

 

로 할 수 있으며 i번째 지점을 트럭으로 배송하거나 헬기로 어떤 지점에 물건을 나르고 그 지점에서 i번째 지점으로 트럭이 오는 경우로 나눠 계산하게 된다.

 

헬기로 배송한다고 했을 때 가장 이득을 보는 위치는 어떤 구간을 배송하기 위해 헬기를 이용할 때 그 구간의 중간 지점이 된다.

 

그렇게 해야 헬기로 배송한 지점에서 다른 지점으로 배달하려는 거리의 합이 최소가 되기 때문이다. (편의점 2 참조)

 

이렇게 구간의 중간 지점을 구해야 하므로 주어진 지점 정보들은 거리순으로 정렬되어야만 한다.

 

최적해 계산은 이중 반복문을 통해 이루어진다.(i번째 지점까지 배송하면서 헬기를 j ~ i 구간 배송에 이용할 때)

 

헬기를 이용할 때 비용은 누적 합으로 미리 저장하여 계산을 빠르게 할 수 있다.

 

누적 합 테이블은 다음과 같이 정의한다.

 

prefix[i][j] := i번째 지점에서 j번째 지점까지 배송하는데 드는 비용

 

누적합을 구하고 dp[i] = min(dp[i - 1] + ar[i] * truck_cost, dp[j - 1] + heli_cost + preifx[middle][i] + prefix[middle][j]) 이 계산을 통해 모든 지점에 배송하는 최소 비용을 구할 수 있다.

 

전체 코드

#include <bits/stdc++.h>
     
using namespace std;
 
int stuff[3001];
int n;
int drive, heli;
int dp[3001];
int prefix[3001][3001];
 
inline int getm(int a, int b) { return (a + b) / 2; }
 
int main()
{
    fill(dp + 1, dp + 3001, 1e9 + 1);
    cin.tie(0); ios::sync_with_stdio(false);
    cin >> n;
 
    for (int i = 1; i <= n; ++i)
        cin >> stuff[i];
    cin >> drive >> heli;
    sort(stuff + 1, stuff + 1 + n);
    
    for (int i = 1; i <= n; ++i)
    {
        int crd = stuff[i];
        for (int j = i - 1; j >= 1; --j)
            prefix[i][j] = prefix[i][j + 1] + abs(crd - stuff[j]) * drive;
        for (int k = i + 1; k <= n; ++k)
            prefix[i][k] = prefix[i][k - 1] + abs(stuff[k] - crd) * drive;
    }
    
    for (int i = 1; i <= n; ++i)
    {
        dp[i] = drive * stuff[i] + dp[i - 1];
 
        for (int j = i; j > 0; --j)
            dp[i] = min(dp[i], dp[j - 1] + heli + prefix[getm(i, j)][i] + prefix[getm(i, j)][j]);
    }
 
    cout << dp[n];
}