[C++] BOJ 8980 택배
그리디 알고리즘인걸 알아도 접근하기 되게 어려운 문제다. [회의실배정] 과 유사한 문제이니 같이 풀어보면 도움이 될 것 같다.
이 문제는 ‘트럭 한대로 배송할 수 있는 최대 박스 수’ 를 구하기 위해 해당 마을에서 택배를 실을 수 있는 만큼 꽉꽉 담으면 문제를 해결할 수 있을거 같지만 아래와 같은 반례가 있다.
// Case:01
1 4 30
// Case:02
2 3 20
3 4 20
따라서 택배의 우선순위를 택배를 보내는 마을을 기준으로 하면 안되고 택배를 받는 마을을 기준으로 해야한다. 택배를 받는 마을을 기준으로 정렬해주고, 정렬 된 순서대로 택배를 실고 내리기 전까지 모든 마을에 가중치를 추가해주면 해결할 수 있다.
#include<bits/stdc++.h>
using namespace std;
int n, MAX, m, from, to, box, weight[2002], res;
vector<tuple<int, int, int>> v;
int main() {
cin.tie(NULL);
ios_base::sync_with_stdio(false);
cin >> n >> MAX >> m;
for (int i = 0; i < m; i++) {
cin >> from >> to >> box;
v.push_back({to, from, box});
}
sort(v.begin(), v.end());
for (int i = 0; i < m; i++) {
int temp = 0;
auto &[t, f, b] = v[i];
for (int j = f; j < t; j++)
temp = max(temp, weight[j]);
int able_weight = min(b, MAX - temp);
res += able_weight;
for (int j = f; j < t; j++)
weight[j] += able_weight;
}
cout << res;
return 0;
}