[백준 8980 번] 택배

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

학교 알고리즘 시간에 그리디를 배우고 있어서 문제를 풀어봤다.
분할 가능한 배낭문제 인것 같다.

풀이 과정

1. 도착 시간이 빠른 순서대로 정렬한다.
2. 같을 경우, 출발 시간은 같은 순서대로 정렬한다.
3. 출발~도착까지의 적재 가능한 양보다 적으면 박스의 무게만큼 더한다.
   3-1. 만약 적재 가능한 양보다 크다면 가능한 만큼만 쪼개서 더한다.
4. 반복한다.

구현

import java.util.*;

class boxes implements Comparable<boxes> {
    int start;
    int end;
    int weight;

    public boxes(int s, int e, int w) {
        start = s;
        end = e;
        weight = w;
    }

    @Override
    public int compareTo(boxes o) {
        if (this.end == o.end) {
            return this.start - o.start;
        }
        return this.end - o.end;
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int c = sc.nextInt();
        int m = sc.nextInt();

        boxes[] boxes = new boxes[m];
        for (int i = 0; i < m; i++) {
            boxes[i] = new boxes(sc.nextInt(), sc.nextInt(), sc.nextInt());
        }

        Arrays.sort(boxes);

        int[] village = new int[n + 1];
        int cnt = 0;

        for (boxes box : boxes) {
            int maxC = c;

            for (int i = box.start; i < box.end; i++) {
                maxC = Math.min(maxC, c - village[i]);
            }

            int lowWeight = Math.min(box.weight, maxC); //만약 적재량 < 박스 무게라면 박스를 쪼갬.

            for (int i = box.start; i < box.end; i++) {
                village[i] += lowWeight;
            }

            cnt += lowWeight;
        }

        System.out.println(cnt);
    }
}