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;
}