[8980] 택배

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

8980번: 택배

<문제>

구간이 주어지고 이에대한 최적해를 greedy적 접근으로 해결하는 부분은 회의실배정 문제와 같다.

 

회의실배정 문제에서 회의실을 '빨리'끝나는 회의를 먼저 배정하듯, 이 문제도 도착이 빠른 택배를 먼저 배송한다.

회의실배정 문제는 회의실 개수의 최대화로, 회의를 배정할때마다 개수만 1 증가시켜주면 되지만

이 문제같은 경우 택배의 개수와, 트럭의 용량을 모두 고려하여 정답을 업데이트해주어야 한다.

 

조건 3: 박스 중 일부만 배송할 수도 있다.

위 조건과 answer의 업데이트를 할때에 고려해주어야 하는 부분때문에 어려웠던 것 같다.

보통 그리디는 아이디어 구상, 접근이 어려운 경우가 많은데 이번 문제는 어째 반대였다.

 

 

<소스코드>

#include<stdio.h>
#include<algorithm>
#include<vector>
using namespace std;
typedef struct { int start, end, value; } info;
vector <info>v;
int n, c, m;
int a[2001];
bool cmp(info a, info b) {//목적지가 빠른순 -> 출발지가 빠른순
    if (a.end == b.end)return a.start < b.start;
    else return a.end < b.end;
}
int main(void) {
    int i, j;
    scanf("%d %d", &n, &c);
    scanf("%d", &m);
    for (i = 0; i < m; i++) {
        int x = 0, y = 0, z = 0;
        scanf("%d %d %d", &x, &y, &z);
        v.push_back({ x,y,z });
    }
    sort(v.begin(), v.end(), cmp);
    int answer = 0;
    for (i = 0; i < v.size(); i++) {
        int curStart = v[i].start;
        int curEnd = v[i].end;
        int next = 0;
 
        for (j = curStart; j < curEnd; j++)
            next = max(a[j], next);
        next = min(c - next, v[i].value);
 
        answer += next;
        for (j = curStart; j < curEnd; j++)
            a[j] += next;
    }
    printf("%d", answer);
    return 0;
}

 

31번라인 : 트럭의 용량을 넘기지 않는 한에서만 택배를 실을 수 있다. 

택배가 존재하지 않는데 실어버리는 문제는 min()안에 같이 넣어서 해결한다.

 

29-30라인 :  택배를 배송하는 구간중 한번이라도 용량을 초과하는 문제가 없도록, 구간중 최대값을 찾으며

구간에 대한 택배용량을 저장하여 이후에 담을 next를 찾기위해, a[]를 선언. 34-35라인으로 업데이트해준다.