8980 - 택배

https://www.acmicpc.net/problem/8980

8980번: 택배

생각해보기

1. 시작은 무조건 1번이므로 최대한 빨리 내리는 것들을 위주로 동작을 하는 것이 이득이다.
2. 정렬을 도착점을 기준으로 진행 해주자.
3. 시작점과 도착점 사이에서 트럭의 용량인 C를 넘는지 확인해주고, 넘지 않는 정도만 담도록 진행한다.
4. 시작점과 도착점 중간에서 대량의 상자를 옮겼을 가능성이 있으므로 중간 과정에서 트럭의 최대 용량을 구한 뒤, 나머지 양을 싣고 출발하자.
5. 사이에서는 그 양만큼 트럭 용량이 증가한 것이므로 전부 증가시켜준다.

코드

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

using namespace std;

typedef struct data{
    int start, end, cost;
}d;

int N,C;
int M;
vector<d> boxes;
int chk[2001];

bool op(d &a, d &b){
    if(a.end == b.end){
        return a.start < b.start;
    }
    return a.end < b.end;
}

void input(){
    int a,b,c;

    cin>>N>>C>>M;
    for(int i=0;i<M;++i){
        cin>>a>>b>>c;

        boxes.push_back({a,b,c});    
    }
}

void solution(){
    int answer = 0;
    sort(boxes.begin(), boxes.end(), op);

    for(int i=0;i<M;++i){
        int start = boxes[i].start;
        int end = boxes[i].end;
        int cost = boxes[i].cost;

        int maxnum = *max_element(&chk[start], &chk[end]);
        int num = min(cost, C-maxnum);

        for(int j=start;j<end;++j){
            chk[j] += num;
        }
        
        answer += num;
    }

    cout << answer;
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    input();
    solution();

    return 0;
}