백준 8980번 택배(C++)🚩

접근 방식

- 택배를 빨리 내릴수 있는걸 우선으로 담아야 최대한 많이 담을수 있다. 처음부터 끝까지 가서 계속 자리만 차지하는

택배를 없애야하는것..

- 정렬해서 처음-도착 위치에 지금 최대 택배를 몇번 담을수 있는지 차례로 계산한다. 

 

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

using namespace std; 

struct info{
    int x;
    int y;
    int z;
}; 

bool cmp(info a, info b){
    
    if(a.y==b.y){
       if(a.z==b.z){
           return a.x<b.x;
       }
       return a.z<b.z;
    }
    
    return a.y<b.y;
}



int main()
{
   vector<info>t;     
    
   int n,w;
   cin>>n>>w;
   int m;
   cin>>m;
   int a,b,c;
   
   for(int i=0;i<m;i++){
       cin>>a>>b>>c;
       t.push_back({a,b,c}); 
   }
   
   sort(t.begin(),t.end(),cmp);

   //시뮬레이션 어케돌림? 
   
   int ans=0; 
   
   //차례로 얼마를 추가할수 있는지 봄 
   
   vector<int>amount(n+1,0);
   
   
   for(int i=0;i<t.size();i++){
       
         int src=t[i].x;
         int dest=t[i].y;
         int weight=t[i].z; 
         
         //현재 트럭에 적재되있는 현황 파악
         int maxs=0;
         for(int j=src;j<dest;j++){
             maxs=max(maxs,amount[j]);
         }
         
         int total=min(w-maxs,weight); 
         
         ans+=total; 
         
         for(int j=src;j<dest;j++){
             amount[j]+=total; 
         }
       
       
   }
   
   cout<<ans;

    return 0;
}