[백준 8980] 택배

문제

백준 8980

유형

• 그리디

풀이

트럭은 일직선으로 계속 이동하고 이전 마을을 다시 돌아가지 않기 때문에 받는 마을이 작은 순으로 정렬해서 배달할 수 있는 만큼 배달해야 최대로 많은 박스를 배송할 수 있다.

먼저 받는 마을이 작은 순으로 정렬한 뒤 각 마을을 트럭의 최대 용량으로 초기화 한다. 그리고 주어지는 배송들을 순회하면서 최대한 많이 실을 수 있는 박스를 실어서 배송한다.

코드

#include <bits/stdc++.h>

using namespace std;
struct pos { 
	int a, b, c; 
} arr[10001];
int n, c, m;

bool cmp(const pos& A, const pos& B) {
	return A.b < B.b;
}

int main() {
	cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(false);
	cin >> n >> c >> m;
	for (int i = 0; i < m; i++) {
		cin >> arr[i].a >> arr[i].b >> arr[i].c;
	}

	sort(arr, arr + m, cmp);
	vector<int> v(2001, c);

	int ans = 0;
	for (int i = 0; i < m; i++) {
		int MIN = 1e9;
		for (int j = arr[i].a; j < arr[i].b; j++) MIN = min(MIN, v[j]);

		if (MIN >= arr[i].c) {
			ans += arr[i].c;
			for (int j = arr[i].a; j < arr[i].b; j++) v[j] -= arr[i].c;
		}
		else {
			ans += MIN;
			for (int j = arr[i].a; j < arr[i].b; j++) v[j] -= MIN;
		}
	}
	cout << ans;


	return 0;
}