8980 ํƒ๋ฐฐ

ํ’€์ด(๊ทธ๋ฆฌ๋””)

1. ๊ฐ ๋„์ฐฉ์ง€๋ณ„๋กœ ์ •๋ณด๋ฅผ ๋”ฐ๋กœ ๊ด€๋ฆฌํ•จ.(๊ฐ™์ดํ•ด๋„ ๋˜๊ธดํ•จ)
2. ๋„์ฐฉ์ง€ 1~N๋ฒˆ๊นŒ์ง€ ์ž…๋ ฅ๋ฐ›์€ C๋กœ ํŠธ๋Ÿญ ์šฉ๋Ÿ‰์„ ์ดˆ๊ธฐํ™”ํ•จ.
3. ๋„์ฐฉ์ง€ 2๋ฒˆ๋ถ€ํ„ฐ ์ •๋ณด๋ฅผ ํ•˜๋‚˜์”ฉ ๋ฝ‘์•„๊ฐ€๋ฉฐ ๊ฒ€์‚ฌ. ์‹œ์ž‘์ง€์ ~ํ˜„์žฌ ๋„์ฐฉ์ง€-1 ๊นŒ์ง€์—์„œ์˜ ์ตœ์†Œ๊ฐ’์„ ๋ฝ‘๊ณ , ๊ทธ๋งŒํผ์„ 2์˜ ๋ฐฐ์—ด์—์„œ ๋นผ์คŒ.(๋ฌผ๋ก  ๊ทธ ์ตœ์†Ÿ๊ฐ’์ด ํ˜„์žฌ ์ •๋ณด์—์„œ์˜ ํƒ๋ฐฐ๋Ÿ‰๋ณด๋‹ค ๋งŽ์œผ๋ฉด ํƒ๋ฐฐ๋Ÿ‰์œผ๋กœ ์ œํ•œ.)

* ์ตœ์†Ÿ๊ฐ’์œผ๋กœ ๋ฝ‘์„ ๊ฒฝ์šฐ, ์ตœ๋Œ€ํ•œ ๋งŽ์ด ๋‹ด๋Š” ๊ฒƒ์ด๋ฏ€๋กœ, ๊ทธ๊ฒƒ์ด ๊ฒฐ๊ตญ ์ตœ๋Œ“๊ฐ’์ด ๋จ.

์ฝ”๋“œ

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
 
vector<pair<int, int>> list[2021];
int N, C, M, capacity[2021];
 
int min(int a, int b) {
	return a < b ? a : b;
}
 
int main() {
	cin >> N >> C >> M;
	for (int i = 0; i < M; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		list[b].push_back({ a,c });
	}
	for (int i = 1; i <= N; i++) {
		capacity[i] = C;
		sort(list[i].begin(), list[i].end());
	}
 
	int shipped = 0;
 
	for (int i = 2; i <= N; i++) {
		for (int j = list[i].size() - 1; j >= 0; j--) {
			int s = list[i][j].first, box = list[i][j].second, m = 2000000000;
			for (int k = s; k < i; k++) {
				m = min(m, capacity[k]);
			}
			int howMany = min(box, m);
			for (int k = s; k < i; k++)
				capacity[k] -= howMany;
			shipped += howMany;
		}
	}
 
 
	cout<< shipped;
}