백준 8980번: 택배 Java Solution

1. Problem Definition & Analysis

박스마다 출발지, 목적지 정보가 있고 최대 트럭 용량까지 박스를 실을 수 있다. 이때 트럭이 처음부터 끝까지 돌아오지 않고 이동할 때 최대로 배송 가능한 박스가 몇 개인지 구하는 문제이다.

이 문제를 잘 생각해보면 마치 그리디 알고리즘의 Well-known case인 Job Scheduling 문제 같다. 이는 각각의 태스크가 시작 시간과 종료 시간을 가질 때 최대한 많이 스케줄링하려면 어떻게 해야 하는가?에 대한 것이다. 대표적으로 회의실 예약에 관한 문제가 있다. 회의실 예약 문제에 대해 먼저 설명해 보겠다.

회의실 예약 문제의 핵심은 끝나는 시간에 대해 오름차순으로 정렬하고 해당 회의가 예약 가능한지(schedulable) 판단하는 것이다. 예약 가능하다면 현재 예약된 회의의 끝나는 시간을 캐싱해 두고 다음 회의를 계속해서 탐색한다. 이 문제의 핵심은 다음과 같은 논리이다.

직관적인 설명은 다음과 같다. 두 회의 $A$, $B$가 있다고 하고, 각각의 시작/종료 시간을 $S_{A}$, $S_{B}$, $E_{A}$, $E_{B}$라고 하자. 만약 $E_{A} < E_{B}$일 때 $B$ 회의를 스케줄링한다면 회의의 시작/종료 시간이 $[E_{A}, E_{B})$ 구간 안에 포함되어 있는 다른 회의($E_{A} \le S_{C} < E_{C} < E_{B}$를 만족하는 회의 $C$)를 스케줄링할 수 없게 된다.

교환 정리를 사용한 조금 더 엄밀한 설명은 다음과 같다.

1. 현재 $A$, $B$, $C$, $...$($E_{A} \le E_{B} \le E_{C} \le ...$)가 스케줄링 가능한 상황이라고 하자. 스케줄링 가능하다는 것은 $S_{A}$, $S_{B}$, $S_{C}$, $...$ 모두 기존의 종료 시간보다 뒤에 있다는 의미이다.
2. 이 중 그리디 알고리즘의 선택인 $A$를 포함하지 않지만 최적인 해 $O$가 존재한다고 가정하며, 최적해에서 가장 빠른 종료 시간을 갖는 선택을 $O_1$이라고 한다.
3. $E_{O_1} \ge E_{A}$이므로, $O$를 통해 도출할 수 있는 해인 $O' = (O - {O_1}) \cup A$ 역시 유효하며 $|O'| = |O|$이므로 최적해이다.
4. 따라서 최소한 하나의 최적해는 $A$를 포함한다.

배달 문제도 이와 마찬가지로 도착지를 기준으로 정렬하는 것이 핵심이다. 그런데 회의실 배정 문제에서는 한 번 스케줄링이 일어나면 충돌하는 스케줄을 고려할 수 없었지만, 배달 문제에서는 트럭의 용량인 $C$가 정의되어 있기 때문에 충돌하는 스케줄도 고려할 수 있다.

예를 들어 $C=30$이고, (출발지, 도착지, 목적지)가 $(1, 9, 20)$, $(2, 10, 20)$인 두 박스 정보가 있다고 하자. $(1, 9, 20)$인 박스를 $20$개 담더라도 $(2, 10, 20)$인 박스도 $10$개 담을 수 있다.

교환 정리는 생략하고, 직관적인 설명을 제시한다. 두 배달 정보 $A$, $B$가 있다고 하고, 각각의 출발지/목적지를 $S_{A}$, $S_{B}$, $E_{A}$, $E_{B}$라고 하자. 만약 $E_{A} < E_{B}$일 때 $B$ 박스를 우선 최대한 담아버린다면 $[E_{A}, E_{B})$ 구간 안에 포함되어 있는 다른 박스($E_{A} \le S_{D} < E_{D} < E_{B}$를 만족하는 박스 $D$)는 전혀 담지 못하거나 충분히 담지 못할 수도 있다.

예를 들어 위 예제에서 $(3, 4, 10)$, $(5, 6, 10)$, $(7, 8, 10)$인 박스 정보 세 개가 추가되었다고 가정하자. $(2, 10, 20)$인 박스를 우선해서 최대한($10$개) 담는다면 이 세 개의 박스를 $10$개씩 담음으로써 얻을 수 있는 최대 결과 $30$를 얻지 못하게 된다(즉, 최적해가 보장되지 않는다).

이 문제가 왜 그리디 문제인지에 대한 설명은 여기까지 하고, 박스를 최대한 많이 담는 방법을 구현하는 과정을 설명하겠다.

1. 트럭이 각 도시 $i$에서 갖고 있는 박스의 개수를 나타내는 상태 배열을 정의한다.
2. 그리디하게 가져온 현재의 박스 정보를 $A(src, dest, count)$라고 하자. $[src, dest)$ 구간에서 트럭이 갖고 있는 박스의 최대 개수를 구한 후 트럭의 용량($C$) 및 박스의 최대 개수($count$)를 고려하여 가장 많이 담을 수 있는 박스의 개수($k$)를 도출한다.
3. $[src, dest)$ 구간에 트럭이 갖고 있는 박스의 개수를 $k$만큼 늘린다(또한, 정답에도 이 수치를 추가한다).

2. Solution

package P8980;

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

public class Main {

    static class Box implements Comparable<Box> {
        int src, dest, count;

        public Box(int src, int dest, int count) {
            this.src = src;
            this.dest = dest;
            this.count = count;
        }

        public int compareTo(Box other) {
            return dest - other.dest;
        }
    }

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;

    static int N, C, M, src, dest, count, maxDelivery;
    static int[] capability;
    static Box[] boxes;

    public static void main(String[] args) throws IOException {
        st = new StringTokenizer(br.readLine());
        N = Integer.parseInt(st.nextToken());
        capability = new int[N + 1];
        C = Integer.parseInt(st.nextToken());
        M = Integer.parseInt(br.readLine());
        boxes = new Box[M];
        for (int i = 0; i < M; i++) {
            st = new StringTokenizer(br.readLine());
            src = Integer.parseInt(st.nextToken());
            dest = Integer.parseInt(st.nextToken());
            count = Integer.parseInt(st.nextToken());
            boxes[i] = new Box(src, dest, count);
        }
        Arrays.sort(boxes);
        for (Box box : boxes) {
            int bound = box.count;
            for (int i = box.src; i < box.dest; i++)
                bound = Math.min(bound, C - capability[i]);
            maxDelivery += bound;
            for (int i = box.src; i < box.dest; i++)
                capability[i] += bound;
        }
        System.out.println(maxDelivery);
    }
}

그리디 알고리즘 특성상 구현 과정은 크게 복잡하지 않으므로 코드에 대한 설명은 생략한다.