문제

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


알고리즘

DP


풀이

헬리콥터는 본점에서 지점으로만 배송이 가능하고 트럭은 본점에서 지점 배송뿐만 아니라 지점에서 지점 사이의 배송이 가능할 때, 최소의 택배비용을 묻고 있습니다.

일단 택배들을 정렬합시다. 10위치의 택배가 2개 있고 30위치의 택배가 하나 있다면 거리 순서대로 처리하는 것이 최적이기 때문입니다. 그 후 $dp[i]$ 가 1번 택배물 부터 $i$번 택배까지 배송했을 때 드는 최소비용이라고 정의합시다. 아마 이전 지점까지의 택배를 모두 해결한 상태인 $dp[i-1]$ + 본점에서 $i$지점까지 트럭으로 배달하는 상태까지는 처리하셨을 겁니다.

문제는 헬리콥터가 $i$지점에 영향을 미치는 경우입니다. $i-1$지점의 택배를 처리할 때 헬기 사용 + $i-1$지점에서 $i$지점까지 트럭, $i-2$지점의 택배를 처리할때 헬기 사용 + $i-2$지점에서 $i$지점까지 트럭사용… 이 때의 $i-1$지점은 어떻게 되는거지? 와 같이 생각할 수 있습니다. 만약 마지막 경우처럼 헬기를 사용하고 $i-2$지점에서 $i$지점까지 트럭을 사용했는데 $i-1$지점에 헬기를 사용해서 배송할 일이 있을까요? 없습니다. 그럴 바엔 $i-1$지점에 헬기를 사용한 후 거기서 $i-2$ 와 $i$를 처리하는 것이 더 이득이기 때문이죠. 즉 헬기가 처리하는 구간은 연속적이여야 합니다. 그 구간에서도 헬기는 중앙에 사용해야만 합니다.

헬기가 영향을 미치는 부분을 for문을 통해 처리합시다. for문 내부의 부분합을 구하기 위해선 선형시간의 복잡도를 요구합니다. 이는 누적합으로 $O(1)$에 처리하게 되면 최종 시간복잡도는 $O(N^2)$에 해결가능합니다.

코드1

#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define REP(i,n) for(int i=1;i<=n;++i)
#define FAST cin.tie(NULL);cout.tie(NULL); ios::sync_with_stdio(false)
using namespace std;

int N, t, h;

int parcel[3001], psum[3001],cache[3001];

int solve(int idx) {
    if (idx == 0) return 0;

    int& ret = cache[idx];
    if (~ret) return ret;

    ret = solve(idx - 1) + parcel[idx]*t;
    for (int i = 1;i <= idx;++i) {
        int mid = (i + idx) / 2;
        int ml = (mid - i + 1) * parcel[mid] - (psum[mid] - psum[i - 1]);
        int mr = psum[idx] - psum[mid - 1] - (idx - mid + 1) * parcel[mid];
        int c = (ml + mr) * t + h;
        ret = min(ret, solve(i - 1) + c);
    }
    return ret;
}

int main() {
    FAST;
    memset(cache, -1, sizeof(cache));
    cin >> N;
    REP(i, N) {
        cin >> parcel[i];
    }
    cin >> t >> h;

    sort(parcel + 1, parcel + 1 + N);
    REP(i, N) {
        psum[i] = psum[i - 1] + parcel[i];
    }
    cout << solve(N);

    return 0;
}

코드 2

#include <bits/stdc++.h>
#define rep(i, n) for (int i = 0; i < n; ++i)
#define REP(i, n) for (int i = 1; i <= n; ++i)
using namespace std;

int N, tr, hl;
int par[3001], psum[3001], cache[3001];
int main() {
#ifndef ONLINE_JUDGE
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    cin.tie(NULL);
    cout.tie(NULL);
    ios::sync_with_stdio(false);

    cin >> N;
    REP(i, N) {
        cin >> par[i];
    }
    cin >> tr >> hl;
    sort(par + 1, par + N + 1);
    REP(i, N) {
        psum[i] = psum[i - 1] + par[i];
    }
    for (int i = 0; i < N; ++i) {
        cache[i + 1] = tr * par[i + 1] + cache[i];
        for (int j = i + 1; j >= 1; --j) {
            int land = (i + 1 + j) / 2;
            int ltcnt = land - j + 1;
            int lt = ltcnt * par[land] - (psum[land] - psum[j - 1]);
            int rtcnt = i + 1 - land + 1;
            int rt = psum[i + 1] - psum[land - 1] - rtcnt * par[land];
            int c = (lt + rt) * tr + hl;
            cache[i + 1] = min(cache[i + 1], c + cache[j - 1]);
        }
    }
    cout << cache[N];
    return 0;
}