백준 8980번 택배

골드4 그리디 알고리즘으로 풀었다.

 

받는 마을 기준으로 정렬을 시킨다. 

 

1 5 10

2 3 40

3 4 40

 

이런경우에도 조건을 만족하려면 받는 마을 기준으로 정렬을 시켜야 최적해를 구할 수 있다.

#include <iostream>
#include <algorithm>
using namespace std;

typedef struct Box {
    int sendi;
    int reci;
    int boxn;
} Box;

bool comp(Box a,Box b)
{
    if(a.reci==b.reci) return a.sendi < b. sendi;
    return a.reci < b.reci;
}

int main()
{
    int n,c;
    int m;
    cin>>n>>c>>m;
    Box arr[m];
    
    for(int i=0;i<m;i++)
    {
        cin>>arr[i].sendi>>arr[i].reci>>arr[i].boxn;
    }
    
    sort(arr,arr+m,comp);
    
    int before=arr[0].sendi; int noww=0; int wbox[3000]={0,}; int sumbox=0;
    
    for(int i=0;i<m;i++)
    {
        int maxv=-1;
        for(int j=arr[i].sendi;j<arr[i].reci;j++)
        {
            if(wbox[j]>maxv)
            maxv=wbox[j];
        }
        if(maxv>=c)
        continue;
        int addv=0;
        if(maxv+arr[i].boxn<=c)
            addv=arr[i].boxn;
        else
            addv=c-maxv;
        for(int j=arr[i].sendi;j<arr[i].reci;j++)
        wbox[j]+=addv;
        sumbox+=addv;
    }
    cout<<sumbox;
}