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

www.acmicpc.net/problem/8980

8980번: 택배

to_from에 ((목적지, 출발지),박스의 개수)를 저장하여 목적지, 출발지 순으로 정렬하고 목적지가 빠른 것부터 현재 택배를 옮기는 구간에서 가장 많이 택배가 쌓여 있을 때를 구해서 트럭에 최대한 쌓을 수 있는 개수를 구한 뒤, 트럭에 최대한 쌓을 수 있는 개수가 택배의 개수보다 작을 때는 지금 택배 개수 전체를 넣을 수 없고, 그렇지 않을 때는 지금 택배 개수 전체를 넣을 수 있다는 것을 이용하여 문제를 해결했다.

 

코드

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

int n, c;
int m;
int result = 0;
vector<pair<pair<int, int>, int>> to_from; //((목적지, 출발지),박스의 개수)를 저장
vector<int>load_info(2001, 0); //각 마을의 위치에서 트럭에 쌓여있는 박스의 개수 저장

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

	cin >> n >> c;
	cin >> m;

	for (int i = 0; i < m; i++)
	{
		int from, to, num;

		cin >> from >> to >> num;

		to_from.push_back(make_pair(make_pair(to, from), num));
	}

	//도착 도시를 기준으로 정렬
	sort(to_from.begin(), to_from.end());

	for (int i = 0; i < to_from.size(); i++)
	{
		int from = to_from[i].first.second;
		int to = to_from[i].first.first;
		int num = to_from[i].second;

		int max_load = 0; //현재 택배를 옮기는 구간에서 가장 많이 택배가 쌓여 있을때를 구한다
		for (int j = from; j <= to - 1; j++)
		{
			max_load = max(max_load, load_info[j]);
		}

		int capacity = c - max_load; //트럭에 최대한 쌓을 수 있는 개수
		int this_load;

		if (capacity < num) //트럭에 최대한 쌓을 수 있는 개수가 택배의 개수보다 작을때 -> 지금 택배 개수 전체를 넣을 수 없다
			this_load = capacity;

		else //지금 택배 개수 전체를 넣을 수 있을때
			this_load = num;

		result += this_load;

		for (int j = from; j <= to - 1; j++)
			load_info[j] += this_load;
	}

	cout << result;

	return 0;
}