1866번 택배

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

dp 다이나믹 동적계획 한국정보올림피아드 복습 필수 추천 코테 생각 prefix sum boj 백준

dp[i] = 1번부터 i번까지 택배를 배달했을 때 최솟값

그렇다면, dp[i]가 될 수 있는 것은 다음 2가지 경우가 있다.

1. i번 째를 택배로 배송 → dp[i] = dp[i - 1] + t * v[i](단, t는 거리에 비례하는 택배 배송비)

2. j ~ i 사이에 임의의 k 점에 대하여 헬리콥터로 배송(단, j <= k <= i)

그렇다면, j와 i 사이에 있는 임의의 k에 대하여 최솟값이 되는 k를 찾아야 하는데

k는 (i + j) / 2가 된다.(이 문제에서 첨부한 첫 번째 코드에서는  (i + j + 1) / 2로 해야 한다.)

첨부한 두 번째 코드는 구간 합을 사용하였는데,

예를 들어

vector v

20(j)   40   50(mid)   60   80(i)

mid를 기준으로 왼쪽 

50 - 20 = 30

50 - 40 = 10

2*50 - (20 + 40) = 40

즉, (mid - j) * v[mid] - (구간 합)

라는 식이 나온다.

Right도 마찬가지이다.(다만, 위의 구간 합이 왼쪽이다.)

#include<bits/stdc++.h>
 
using namespace std;
 
#define Max 3001
 
int n, t, h, dp[Max], prefix_sum[Max];
vector<int> v;
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    scanf("%d", &n);
 
    v.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
        prefix_sum[i] = v[i];
        prefix_sum[i] += prefix_sum[i - 1];
    }
 
    sort(v.begin(), v.end());
 
    scanf("%d %d", &t, &h);
 
    for (int i = 1; i <= n; i++) {
        dp[i] = dp[i - 1] + t * v[i];
        int cost = h;
        // j ~ i 사이에서 적당한 지점((i+j+1)/2)에 대해 모두 계산
        // 예시(i가 5일 때)
        // 5(i) ~ 5(j) → 5(i) ~ 4(j) → 5(i) ~ 3(j)  → ... (전의 계산된 cost가 누적하여 활용됨)
        for (int j = i; j >= 1; j--) {
            // 최소가 되는 지점은 (i + j + 1) / 2이고,
            // 그 지점에서 택배 배달 지역으로 배송(거리 비례 비용 발생)
            // abs(~)는 거리 계산
            cost += abs(v[(i + j + 1) / 2] - v[j]) * t;
            dp[i] = min(dp[i], dp[j - 1] + cost); // j ~ i는 헬리콥터이므로 1 ~ j - 1에 대하여 dp[j - 1]과 cost(헬기)를 활용
        }
    }
 
    printf("%d\n", dp[n]);
 
    return 0;
}

#include<bits/stdc++.h>
 
using namespace std;
 
#define Max 3001
 
int n, t, h, dp[Max], prefix_sum[Max];
vector<int> v;
 
int main()
{
    //freopen("C:\\Users\\park7\\Desktop\\buba.in.6", "r", stdin);
    cin.tie(0);
 
    scanf("%d", &n);
 
    v.assign(n + 1, 0);
    for (int i = 1; i <= n; i++) {
        scanf("%d", &v[i]);
    }
 
    sort(v.begin(), v.end());
 
    for (int i = 1; i <= n; i++) {
        prefix_sum[i] = v[i];
        prefix_sum[i] += prefix_sum[i - 1];
    }
 
    scanf("%d %d", &t, &h);
 
    for (int i = 1; i <= n; i++) {
 
        dp[i] = dp[i - 1] + t * v[i];
 
        for (int j = i; j >= 1; j--) {
            int cost = h;
            int mid = (i + j) / 2;
            int Left = ((mid - j)*v[mid] - (prefix_sum[mid - 1] - prefix_sum[j - 1])) * t;
            int Right = ((prefix_sum[i] - prefix_sum[mid]) - (i - mid)*v[mid]) * t;
 
            dp[i] = min(dp[i], dp[j - 1] + cost + Left + Right);
        }
    }
 
    printf("%d\n", dp[n]);
 
    return 0;
}