BOJ 8980 택배

문제

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

택배의 목록과 트럭의 용량이 정해져 있을 때 배달할 수 있는 택배의 최댓값을 구하는 문제이다.

 

풀이

회의실 문제와 비슷하다.

 

제일 일찍 도착하는 택배 부터 우선순위로 배정해야 한다.

 

<Greedy Choice Property>

문제를 살짝 변형시켜 s부터 e까지 가는 택배 n개가 있으면 s부터 e까지 가는 택배 1개의 선분이 n개 있는 것으로 생각하자.

이제 회의실에서 동시에 C개의 회의를 할 수 있는 회의실 문제로 바뀌었다.

마찬가지로 가장 먼저 끝나는 택배 S, 최적해 M1, M2, M3, ...가 있다고 하면 M1을 항상 S로 바꿔도 최적해 이므로 성립한다.

따라서 무조건 먼저 끝나는 택배를 우선순위로 선택해야 하며, 원래 문제와 똑같아 진다.

 

<Optimal Substructure>

자명하다.

 

*Tip : 내 생각에는 회의실 문제와 비슷한 스타일 문제는 모두 다 정렬 기준을 e -> s의 오름차순이 이득인 것 같다.

시간 복잡도 : $O(NM)$ (아마 더 최적화 할 수 있을 것 같다.)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 2000;
const int MAXM = 10000;

struct Order
{
    int s, e, c;
    bool operator < (const Order& p) const
    {
        if(e == p.e) return s < p.s;
        return e < p.e;
    }
};

int n, c, m;
Order order[MAXM+10];
int ans;

int state[MAXN+10];

int main()
{
    cin.tie(0); cout.tie(0);
    ios_base::sync_with_stdio(false);
    int i, j;

    scanf("%d%d%d", &n, &c, &m);
    for(i=0; i<m; i++) scanf("%d%d%d", &order[i].s, &order[i].e, &order[i].c);
    sort(order, order+m);

    for(i=0; i<m; i++)
    {
        int t = 0;
        for(j=order[i].s; j<order[i].e; j++) t = max(t, state[j]);

        if(t==c) continue;
        int val = min(order[i].c, c-t);
        for(j=order[i].s; j<order[i].e; j++) state[j] += val;
        ans += val;

        //printf("%d %d %d %d\n", order[i].s, order[i].e, order[i].c, val);
    }

    printf("%d", ans);
}