[백준 알고리즘] 8980 c++ 택배

 

그리디하게 풀 수 있는 문제

-> 회의실 배정 문제의 확장된 버전

 

---

 

1. 택배 배달이 먼저 끝나는 순으로 오름차순 정렬

2. 반복문에서, 택배의 최대 용량에 맞춰서 weight 배열에 마을 시점의 용량 기록

3. weight 배열에서 시작지점(택배의 출발 장소) 부터 도착 지점(택배의 도착 장소)-1 인덱스까지 배열에 더하기

4. weight 배열의 각 노드에 택배의 용량을 추가 할 때, 정답 변수에도 용량 추가

 

---

 

#include <iostream>
#include <vector>
#include <algorithm>

int main() {
	std::ios::sync_with_stdio(0);
	std::cin.tie(0);

	int n, m, t;
	std::cin >> n >> m >> t;

	std::vector<std::pair<std::pair<int, int>, int>> list(t, { {0,0}, 0 });
	std::vector<int> w(n + 1, 0);
	int ans = 0;

	for (int i{ 0 }; i < t; i++) {
		std::cin >> list[i].first.second >> list[i].first.first >> list[i].second;
	}

	std::sort(list.begin(), list.end());

	for (int i{ 0 }; i < t; i++) {
		bool check = true;
		int maxCheck = 0;
		for (int j{ list[i].first.second }; j<= list[i].first.first; j++) {
			if (w[j] + list[i].second > m) {
				check = false;
				maxCheck = std::max(w[j], maxCheck);
			}
		}

		if (check) {
			for (int j{ list[i].first.second }; j < list[i].first.first; j++) {
				w[j] += list[i].second;
			}
			ans += list[i].second;
		}
		else {
			for (int j{ list[i].first.second }; j < list[i].first.first; j++) {
				w[j] += m - maxCheck;
			}
			ans += m - maxCheck;
		}
	}

	std::cout << ans << "\n";
}