[BOJ] 택배

[BOJ] 택배

Problem URL : 택배

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

using namespace std;
int capacity[2001];

struct box {
    int u, v, num;
};
bool cmp(box& b1, box& b2) {
    if (b1.v == b2.v) return b1.u > b2.u;
    else return b1.v < b2.v;
}
int main(void) {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    int n, c, m; 
    cin >> n >> c >> m;
    vector<box> v;
    for (int i = 0; i < m; i++) {
        box B;
        cin >> B.u >> B.v >> B.num;
        v.push_back(B);
    }
    sort(v.begin(),v.end(), cmp);
    int ans = 0;
    for (int i = 0; i < v.size(); i++) {
        int maxCapacity = 0;
        for (int j = v[i].u; j < v[i].v; j++) {
            maxCapacity = max(maxCapacity, capacity[j]);
        }
        int addNum = min(c - maxCapacity, v[i].num);
        for (int j = v[i].u; j < v[i].v; j++) {
            capacity[j] += addNum;
        }
        ans += addNum;
    }
    cout << ans;
}

Comments

도착마을이 작은(빠른) 번호일수록 그리디 성격에 부합한다.
만약 도착마을이 같은 번호이면 시작 마을을 큰(늦은) 번호로 선택해준다.