[BOJ 8980] 택배

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

8980번: 택배

Tag : Greedy

 

문제요약

(보내는 마을 번호, 도착하는 마을 번호, 보내는 상자의 수)를 의미하는 (s,e,v) 쌍 M개와 트럭의 최대 용량 C가 주어질 때

배송할 수 있는 최대 박스 수를 구하는 문제다.

 

풀이

(s,e,v)를 (s,e,1) v개로 쪼개보자. 그러면 회의실이 C개인 회의실 배정 문제로 환원된다.

 

* 회의실 배정 문제는 (s,e)에서 e가 작은걸 우선으로 회의를 진행하는 그리디가 성립한다. 

흔히 그리디를 증명하는 방법 중에 A보다 우선순위가 낮은 B를 선택하는 최적해가 있다고 가정한 후

B를 A로 대체해도 여전히 최적해이거나 더 나은 해를 얻을 수 없음을 보이는 방법이 있다. 

+ 리프가 이런걸 exchange argument라고 부른다고 알려줬다.

 

위 그림에서 NOW직후에 \(B.e>A.e\)인 회의 B를 고르는 최적해가 존재한다고 가정하자.

NOW직후의 회의를 고르기 때문에 구간 \([NOW,B.s]\)에 회의는 존재하지 않는다.

(있다면 NOW 직후에 B를 고르는건 최적해는 아니기 때문에 가정에 모순임)

그렇기 때문에 회의 B를 A로 대체해도 최적해에 아무런 영향을 끼치지 않는다.

 

시간복잡도 : \(O(NM)\)

 

전체코드

#include "bits/stdc++.h"
#define pb push_back
#define fi first
#define se second
#define all(x) ((x).begin()), ((x).end())
#define compress(x) sort(all(x)), (x).erase(unique(all(x)),(x).end())
#define siz(x) ((int)((x).size()))
#define endl '\n'
using namespace std;
using ll = long long;
using pi = pair<int,int>;
using pl = pair<ll,ll>;
template<typename T>T rmin(T &a,T b){return a=min<T>(a,b);}
template<typename T>T rmax(T &a,T b){return a=max<T>(a,b);}



int main(){
    ios::sync_with_stdio(0);cin.tie(0);
    
    ll N,K,M;cin>>N>>K>>M;
    struct p{ll s,e,v;};
    vector<p>v(M);
    for(auto&[s,e,v]:v)cin>>s>>e>>v;
    sort(all(v),[&](p&a,p&b)->int{return pi(a.e,a.s)<pi(b.e,b.s);});
    vector<ll>dp(N+1);
    ll ans=0;
    for(int i=0;i<M;i++){
        ll mx=*max_element(dp.begin()+v[i].s,dp.begin()+v[i].e+1),now=0;
        now=min(K-mx,v[i].v);
        ans+=now;
        for(auto j=v[i].s;j<v[i].e;j++)dp[j]+=now;
    }
    cout<<ans<<endl;
}