[C++] 백준 8980번 택배

트럭 한대로 한번 한번 이동했을 때 최대 배송할 수 있는 박스 수를 출력하는 문제입니다.

발송위치에서 수신위치로 박스를 보내는데
수신위치를 기준으로 오름차순 정렬을 해줍니다.

차례대로 보낼 수 있는량을 갱신하면서 하는데 예로 설명을 드리겠습니다.

https://www.acmicpc.net/board/view/6327에 올려주신 예제를 참고 했습니다.

다음처럼 입력 받았을때
6 60
5
1 2 30
2 5 70
5 6 60
3 4 40
1 6 40

정렬을하면 다음과 같습니다.

1 2 30
3 4 40
2 5 70
1 6 40
5 6 60

1 2 30
30 0 0 0 0 0
(+30 적재)

3 4 40
30 0 40 0 0 0
(+40 적재)

2 5 70
30 20 60 20 0 0
(+20 적재)

1 6 40
30 20 60 20 0 0

5 6 60
30 20 60 20 60 0
(+60 적재)

발송위치부터 수신위치까지 이동가능한 최대의양을 옮겨주고
그 값(X)을 그 길에 흐르고 있다고 추가해줘서
다음번 그곳을 거쳐서 가게 될 때는 이미 X만큼 배송중이므로
적재가능량 - X 만큼만 보낼 수 있게 됩니다.

#include <iostream>
#include <cstring>
#include <algorithm>
#include <string>
#include <vector>
#include <queue>
using namespace std;

bool compare(const pair<pair<int, int>, int > &a, const pair<pair<int, int>, int > &b)
{
	if (a.first.second == b.first.second) {
		return a.first.first < b.first.first;
	}
	return a.first.second < b.first.second;
}

int main(int argc, char* argv[])
{
	int n, c;
	int m;
	int x, y, z;
	int get;
	int s, e;
	int capacity = 0;
	int result = 0;
	int truck[2001];
	vector<pair<pair<int, int>, int> > v;	// 출발 도착 용량

	memset(truck, 0, sizeof(truck));

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

	while (m--) {
		cin >> x >> y >> z;
		
		v.push_back({ {x, y}, z });
	}

	sort(v.begin(), v.end(), compare);

	for (int i = 0; i < v.size(); ++i) {
		get = 0;
		s = v[i].first.first;
		e = v[i].first.second;
		capacity = v[i].second;

		for (int j = s; j < e; j++) {
			get = max(get, truck[j]);
		}

		get = min(c - get, capacity);
		result += get;

		for (int j = s; j < e; j++) {
			truck[j] += get;
		}
	}

	cout << result << endl;

	return 0;
}