백준1866 택배

작성일 | In

문제 링크

  • http://icpc.me/1866

문제 출처

  • 2006 KOI 지역 본선 중등부5

사용 알고리즘

  • DP

시간복잡도

  • O(n2)

풀이

dp[i] = 1번째부터 i번째까지 택배를 배달했을 때 최솟값 이라고 정의합시다. 점화식을 Naive하게 채우면 O(n3)이 들게 됩니다. 이 글에서는 먼저 O(n3)으로 구현을 한 뒤, 복잡도를 O(n2)으로 줄여보도록 하겠습니다.

문제를 잘 관찰해보면 헬리콥터를 이용해 배송하는 것은 연속해서 배치되어있는 택배에 적용하는 것이 최적임을 알 수 있습니다. 그러므로 택배들의 위치를 정렬해줍시다.

dp[i-1]까지 모두 구해놓은 상태에서 dp[i]를 구해야 하는 상황을 가정해봅시다. 할 수 있는 동작은 크게 두 가지로 나뉘게 됩니다.

  1. i번째 택배를 트럭으로 운송
  2. i 이하의 적당한 j를 잡아 j부터 i까지 헬리콥터로 운송

트럭의 비용을 t, 헬리콥터의 비용을 h, i번째 택배의 위치를 arr[i]로 잡은다면, 첫 번째 행동은 dp[i] = dp[i-1] + arr[i] * t 로 쉽게 계산할 수 있습니다.
두 번째 경우는 한 가지 관찰이 더 필요합니다. 연속해서 배치되어있는 m개의 택배를 헬리콥터로 운송할 때는 가운데 있는 택배의 위치에 내리는 것이 최적임을 알 수 있습니다.
그 이유는 만약 택배의 개수가 홀수인 경우 그래프는 아래와 같이 그려지게 됩니다.

짝수인 경우 그래프는 아래와 같이 그려지게 됩니다.

그러므로 (i+j)/2 번째 택배의 위치까지 헬리콥터를 이동시키면 됩니다.

점화식을 채워봅시다.

1
2
3
4
5
6
7
8
9
10
for(int i=1; i<=n; i++){
  dp[i] = dp[i-1] + arr[i] * t;
  for(int j=i; j>=1; j--){
    int mid = (i+j)/2;
    int cost = 0;
    for(int k=j; k<=i; k++) cost += abs(arr[mid] - arr[k]) * t;
    cost += h;
    dp[i] = min(dp[i], dp[j-1] + cost);
  }
}

이렇게 점화식을 채우게 되면 최악의 경우에 O(n3)이 걸리게 됩니다. n은 최대 3000이기 때문에 복잡도를 줄여야 합니다.

mid를 기준으로 왼쪽과 오른쪽으로 나눠봅시다.
왼쪽에 있는 택배들은 mid보다 좌표가 작고, 오른쪽은 mid보다 좌표가 큽니다.

이를 이용하여 왼쪽에 있는 택배들은 arr[mid] * (mid-j+1)에서 j부터 mid까지 좌표의 합을 빼준 값에 t를 곱하면 비용이 나오게 됩니다.
반대로, 오른쪽에 있는 택배들은 mid부터 j까지 좌표의 합에서 arr[mid] * (i-mid+1)를 빼준 값에 t를 곱하면 됩니다.

prefix sum을 이용하면 O(n2)만에 구할 수 있습니다.

전체 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include <bits/stdc++.h>
using namespace std;

int main(){
	int n; cin >> n;
	vector<int> arr(n+1), dp(n+1), sum(n+1);

	for(int i=1; i<=n; i++) cin >> arr[i];
	sort(arr.begin()+1, arr.end());
	for(int i=1; i<=n; i++) sum[i] = sum[i-1] + arr[i];

	int t, h; cin >> t >> h;

	for(int i=1; i<=n; i++){
		dp[i] = dp[i-1] + arr[i] * t;
		for(int j=i; j>=1; j--){
			int mid = (i+j) >> 1;

			int left = (arr[mid] * (mid-j+1) - (sum[mid] - sum[j-1])) * t;
			int right = ((sum[i] - sum[mid-1]) - (arr[mid] * (i-mid+1))) * t;

			int cost = left + right + h;
			dp[i] = min(dp[i], dp[j-1] + cost);
		}
	}

	cout << dp[n];
}