[BOJ] 8980. 택배 (📦, 그리디)

🔗

풀이

이 문제는 최대한 많이 배달해야 하므로 빨리 배달할 수 있는 것들부터 빨리 배달할 수록 많이 배달할 수 있다.

(1) 보내는 곳에서 받는 곳까지의 거리가 가장 짧은 순 (2) 택배의 개수의 크기가 큰 순서대로 정렬해야 된다고 생각했다. 근데 애초에 (2)는 고려할 필요가 없는 대상이었고, (1) 같은 경우는 아래와 같이 되는데

Arrays.sort(boxInfo, (a, b) -> {
    return (a[1] - a[0]) - (b[1] - b[0]);
});

이렇게하면 52점에서 통과를 못한다.

근데 잘 생각해보면 도착하는 곳이 항상 출발하는 곳보다 숫자가 크다고 했으므로 a[1] 은 항상 a[0] 보다 크고, b[1] 은 항상 b[0] 보다 크다. 결국 a[1] - a[0] 은 항상 양수가 되고 b[1] - b[0] 도 마찬가지이므로 두 인덱스 중 하나만 가지고 비교하면 되는 것이다.

Arrays.sort(boxInfo, (a, b) -> {
    return a[1] - b[1];
});

이러면 100점된다.

결국 출발지~도착지 사이의 간격이 좁다는 거나 도착지가 앞쪽에 있는거나 같다는 의미가 될 수 있다. 도착지가 1에 가까울 수록 출발지와 도착지의 간격이 짧아진다는 의미. 상식적으로 생각해보면 도착지가 3인게 도착지가 6인 것보다 출발지와의 간격이 짧을 것이다.

import java.io.*;
import java.util.*;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int C = Integer.parseInt(st.nextToken());
        int M = Integer.parseInt(br.readLine());

        int[][] boxInfo = new int[M][3];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            boxInfo[i][0] = Integer.parseInt(st.nextToken());
            boxInfo[i][1] = Integer.parseInt(st.nextToken());
            boxInfo[i][2] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(boxInfo, (a, b) -> {
            return a[1] - b[1];
        });

        long[] road = new long[N];
        long totalCnt = 0;
        for (int[] box : boxInfo) {
            int from = box[0];
            int to = box[1];
            int count = box[2];

            long maxCnt = 0;
            for (int i = from; i < to; i++) {
                maxCnt = Math.max(maxCnt, road[i]);
            }
            
            long add = Math.min(count, C - maxCnt);
            for (int i = from; i < to; i++) {
                road[i] += add;
            }
            totalCnt += add;
        }
        System.out.println(totalCnt);
    }
}