백준 1866 / C++

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

1866번: 택배

 

[ 풀이 ] 

관찰을 통해 인접한 값들끼리, 그리고 그 거리들이 멀수록 헬기로 옮기는게 좋음을 알 수 있다. 

정렬한 후 앞에서부터 트럭으로 옮길지 헬기로 옮길지 정해주자.

또한 옮기는 위치도 결정해줄 수 있다. 

d1, d2 , .... , di를 골라서 옮겼다고 할 때 헬스가 x지점에 내려주면 트럭으로 움직여야 하는 거리는

f(x)=sum(|x-d_i|)가 된다. 이 함수는 중간지점에서 최솟값을 갖는 사실은 잘 알려져 있다. 

dp[i]를 i번째까지 옮긴 최소비용이라 하자.

1. dp[i]=dp[i-1]+T*a[i]: 이건 트럭으로 그냥 옮긴 것이다.

2. j<i에 대해 dp[j]까진 트럭으로, j+1부터 i까진 헬기로 옮기는 것이다.

2번에서 j+1~i번의 절댓값 함수를 처리할때 누적합으로 O(1)에 해주자. O(N^2)에 문제를 풀 수 있다. 

 

[ Code ] 

#include <bits/stdc++.h>
using namespace std;
int n, T, H, dp[3003], a[3003], psum[3003];

// |x-a[s+1]|+...+|x-a[e]| min : x=a[(s+e+1)/2] 일 때 
int func(int s, int e) {
	int mid = (s + e + 1) >> 1;
	return T * ((2 * mid - s - e) * a[mid] + psum[s] + psum[e] - 2 * psum[mid]);
}

int main() {
	ios::sync_with_stdio(0), cin.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++)cin >> a[i];
	sort(a + 1, a + n + 1);
	for (int i = 1; i <= n; i++) {
		psum[i] = psum[i - 1] + a[i];
	}
	cin >> T >> H;
	// dp
	for (int i = 1; i <= n; i++) {
		dp[i] = dp[i - 1] + T * a[i];
		for (int j = 0; j < i; j++) {
			dp[i] = min(dp[i], dp[j] + func(j, i) + H);
		}
	}
	cout << dp[n];
}