[백준/BOJ] 백준 1866번 : 택배

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

1866번: 택배

순서대로 해당 번째 물건까지 배송했을 때 최소 비용을 cache[해당 번째]에 저장하여 문제를 해결했다. 해당 번째 물건마다 해당 물건을 트럭으로 옮기는 경우와, 해당 물건(i번째)과 해당 물건 이하(i이하)의 구간(i이하(j) ~ i)의 경우에서 해당 구간의 물건들을 (j+i)/2번째에 헬리콥터로 옮기고 트럭으로 분배하는 경우를 고려하여 문제를 해결했다. 헬리콥터로 옮기고 트럭으로 분배하는 경우 계산은 누적합을 이용했다

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
vector<int> item(10005, 0);
int t_cost, h_cost;

vector<int> cache(10005, 0); //cache[i] = item[i]번째 물건까지 배송했을때 최소 비용
vector<int> psum(10005, 0); //누적합

int main()
{
	cin.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;

	for (int i = 1; i <= n; i++)
	{
		int input;
		cin >> input;

		item[i] = input;
	}

	sort(item.begin() + 1, item.begin() + (n + 1));

	//누적합을 저장
	for (int i = 1; i <= n; i++)
	{
		psum[i] = psum[i - 1] + item[i];
	}

	cin >> t_cost >> h_cost;

	for (int i = 1; i <= n; i++)
	{
		//i번째 아이템을 트럭으로 옮기는 경우
		int cost_sum = cache[i - 1] + (item[i] * t_cost);

		//j~i번째 구간의 아이템을 (j+i)/2에 헬리콥터로 옮기고 트럭으로 옮기는 경우
		for (int j = 1; j <= i; j++)
		{
			int mid = (i + j) / 2;
			int this_cost_sum = 0;
			this_cost_sum += h_cost;
			this_cost_sum += ((item[mid] * (mid - j)) - (psum[mid - 1] - psum[j - 1])) * t_cost;
			this_cost_sum += ((psum[i] - psum[mid]) - (item[mid] * (i - mid))) * t_cost;

			cost_sum = min(cost_sum, cache[j - 1] + this_cost_sum);
		}

		cache[i] = cost_sum;
	}

	cout << cache[n] << "\n";

	return 0;
}