[BOJ] 백준 8980 택배

출처: https://www.acmicpc.net/problem/898

 Input 

4 40

6

3 4 20

1 2 10

1 3 20

1 4 30

2 3 10

2 4 20

 

 Output 

70

 

트럭이 이동할 때, 도착지가 가까울수록 짐 공간을 점유하는 시간이 적으므로 좋습니다.

따라서 최대한 많이 싣기 위해서는 도착지가 가까운 순 (동일한 경우, 출발지가 빠른 순으로 박스 정렬)

박스를 실을 수 있는 개수가 한정적이므로 최대한 많은 박스를 실을려고 시도합니다. (일부 박스만 배달 가능)

* 트럭이 마을 지나갈 때 짐이 얼마나 있는지 확인

① 개수 = 10, 배달 구간 = 1 → 2  

    현재 트럭에 실린 짐이 없으므로 모두 싣습니다.

② 개수 = 20, 배달 구간 = 1 → 3

    트럭에 실린 양은 10개 이므로 남은 용량은 40(C) - 10 = 30

    박스 개수는 20개 이므로 모두 실을 수 있습니다.

    따라서 현재 트럭에 실린 양은 10 + 20

③ 개수 = 10, 배달 구간 = 2 → 3  

    구간 [2, 3)에서 트럭에 실려 있는 양은 20개 이므로

    남은 용량 40 - 20 = 20 > 10 이므로 모두 실을 수 있습니다.

④ 개수 = 20, 배달 구간 = 2 → 4  

    구간 [2, 4)에서 트럭에 이미 20 + 10 = 30개가 실려 있으므로

    남은 용량 = 40 - 30 = 10 < 20 이므로 20개 중 일부에 해당하는 10개만 실을 수 있습니다.

⑤ 개수 = 30, 배달 구간 = 1 → 4  

    구간 [1, 4)에서 특정 구간이 이미 용량이 꽉 찬 곳이 있으므로 실을 수가 없습니다.

⑥ 개수 = 20, 배달 구간 = 3 → 4

    구간 [3, 4)에서 트럭에 실린 양은 10으로 남은 용량 40 - 10 = 30 > 20 이므로 모두 실을 수 있습니다.

트럭에 싣기만 하면 배달이 된 것이므로 10 + 20 + 10 + 10 + 20 = 70

 

세그먼트 트리 (with Lazy Propagation)을 이용한 풀이

[BOJ] 백준 8980 택배

 

---

#include <stdio.h>
const int MAX_N = 2000 + 5;
const int MAX_M = 10000 + 5;
inline int max(int A, int B) { if (A > B) return A; return B; }
inline int min(int A, int B) { if (A < B) return A; return B; }
 
struct Box {
    int from, to, cnt;
} box[MAX_M], trr[MAX_M];
 
int comp(Box X, Box Y) {
    if (X.to == Y.to) return  X.from < Y.from;
    else return X.to < Y.to;
}
 
// 구간별로 트럭이 들고 있는 상자 개수
int truck[MAX_N];
int N, C, M, ans;
 
void input() {
    scanf("%d %d %d", &N, &C, &M);
    for (int i = 0; i < M; ++i)
        scanf("%d %d %d", &box[i].from, &box[i].to, &box[i].cnt);
}
 
void mergeSort(int start, int end) {
    if (start >= end)
        return;
    int mid = (start + end) / 2;
    mergeSort(start, mid);
    mergeSort(mid + 1, end);
    int i = start, j = mid + 1, k = start;
    while (i <= mid && j <= end) {
        if (comp(box[i], box[j]) > 0)
            trr[k++] = box[i++];
        else
            trr[k++] = box[j++];
    }
    while (i <= mid) trr[k++] = box[i++];
    while (j <= end) trr[k++] = box[j++];
    for (i = start; i <= end; ++i)
        box[i] = trr[i];
}
 
void solve() {
    int min = 0x7fffffff, cnt;
    for (int i = 0; i < M; i++) {
        // 선택한 상자
        min = box[i].cnt;
        // [s, e) 마을까지 모든마을에 걸쳐 실을수 있는 상자수는?
        for (int j = box[i].from; j < box[i].to; j++) {
            cnt = C - truck[j];
            // 상자의 최대 갯수를 넘길 수 있기 때문에
            // 지금 싣고자 하는 박스 개수와 실제 트럭에 싣을 수 있는 개수 중 작은 것 선택
            if (min > cnt) min = cnt;
        }
        ans += min;
        // 실을수 있는 상자를 [s, e)까지 실어놓는다
        for (int j = box[i].from; j < box[i].to; j++) {
            // 구간에 선택된 박스 개수 추가
            truck[j] += min;
        }
    }
}
 
int main() {
    // freopen("input.txt", "r", stdin);
    input();
    mergeSort(0, M - 1);
    solve();
    printf("%d\n", ans);
}