[백준 JAVA] 8980 : 택배

[백준 8980] 택배 : https://www.acmicpc.net/problem/8980

---

문제 조건 정리

 

1. 트럭은 본부에서 출발하여 1번 마을부터 마지막 마을까지 오른쪽으로 가면서 마을에 있는 물건을 배송한다.
   
   
2. 각 마을은 배송할 물건들을 박스에 넣어 보내며, 본부에서는 박스를 보내는 마을번호, 박스를 받는 마을번호와 보낼 박스의 개수를 알고 있다.
3. 박스들은 모두 크기가 같다.
4. 트럭에 최대로 실을 수 있는 박스의 개수, 즉 트럭의 용량이 있다.
5. 이 트럭 한 대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 한다.

• 조건 1: 박스를 트럭에 실으면, 이 박스는 받는 마을에서만 내린다.
• 조건 2: 트럭은 지나온 마을로 되돌아가지 않는다.
• 조건 3: 박스들 중 일부만 배송할 수도 있다.

---

입력

 

1. 박스를 받는 마을번호는 보내는 마을번호보다 크다. 
   
   이외 별로 중요하지 않다고 생각함.

---

문제를 풀기 전

 

1. 부분 배낭과 비슷한 느낌으로 푸는 건가? -> 택배에 가치가 없음. 한계만 정해져 있으므로 다른 방법이 있을 듯
   
   
2. 예시를 생각하다보니 택배 정보를 출발 마을이나 도착 마을을 기준으로 정렬하면 될 것 같다고 생각함
   
   
3. 택배 정보를 출발 마을을 기준으로 정렬한다면,
   첫 택배 정보가 최악의 경우 첫 마을에서 마지막 마을까지 트럭의 최대 용량을 담을 수 있음.
   
   
4. 택배 정보를 도착 마을을 기준으로 정렬한다면,
   최악의 경우에도 다음 도착 마을로 향하는 택배 정보에 영향을 미치지 않음 -> 그리디
   
   (최악의 경우, 예시)
   도착 마을을 기준으로 정렬된 첫 택배 정보가 1번 마을 ~ n번 마을로 향할 때, 트럭의 최대 용량을 담아도
   n+1번째 마을부터 출발하는 택배에게 영향을 미치지 않음
   
   
5. 이외에, 부분적으로 택배를 담을 수 있는 것을 체크하는 로직을 추가하면 될 듯

 

---

코드

 

package baekJoon;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.StringTokenizer;

public class BJ8980 {

    static private class Delivery {
        int start, end, count;

        public Delivery(int start, int end, int count) {
            this.start = start;
            this.end = end;
            this.count = count;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");

        int townCount = Integer.parseInt(stringTokenizer.nextToken());
        int capacity = Integer.parseInt(stringTokenizer.nextToken());

        List<Delivery> deliveries = new ArrayList<>();

        int n = Integer.parseInt(bufferedReader.readLine());
        for (int i = 0; i < n; i++) {
            stringTokenizer = new StringTokenizer(bufferedReader.readLine(), " ");
            int start = Integer.parseInt(stringTokenizer.nextToken());
            int end = Integer.parseInt(stringTokenizer.nextToken());
            int count = Integer.parseInt(stringTokenizer.nextToken());

            deliveries.add(new Delivery(start, end, count));
        }

        // 도착 마을을 기준으로 정렬
        // 도착마을이 같다면 시작 마을을 기준으로 정렬
        deliveries.sort((a, b) -> {
            if (a.end == b.end) return a.start - b.start;
            return a.end - b.end;
        });

        int[] truckCapacity = new int[townCount + 1]; // 마지막 도시는 필요없음
        Arrays.fill(truckCapacity, capacity);
        int answer = 0;

        for (int i = 0; i < n; i++) {
            // 현재 택배 정보
            Delivery curr = deliveries.get(i);

            // 현재 트럭이 해당 마을로 갔을 때, 해당 마을에서 담을 수 있는 택배의 개수 중 *최소값*
            // 즉, 현재 트럭이 해당 경로에서 담을 수 있는 최대 택배 개수
            int minCapacity = Integer.MAX_VALUE;

            // 도착 마을은 택배를 내리므로 확인하지 않음
            for (int s = curr.start; s < curr.end; s++) {
                minCapacity = Math.min(minCapacity, truckCapacity[s]);
            }

            // 트럭이 실을 수 있는 택배의 양이 현재 택배 수보다 적다면
            if (minCapacity < curr.count) {
                answer += minCapacity; // 실을 수 있는 만큼만 싣는다

                // 현재 택배 경로 동안
                for (int s = curr.start; s < curr.end; s++) {
                    truckCapacity[s] -= minCapacity; // 실은 개수만큼 실을 수 없음
                }
            }
            // 트럭이 모든 택배를 실을 수 있다면
            else {
                answer += curr.count; // 모두 싣는다

                // 현재 택배 경로 동안
                for (int s = curr.start; s < curr.end; s++) {
                    truckCapacity[s] -= curr.count; // 실은 개수만큼 실을 수 없음
                }
            }
        }

        System.out.println(answer);

    }
}

 

---

문제를 풀고 난 후

 

1. 트럭이 해당 마을, 즉 경로이자 시점에서 택배를 얼마나 실었는지, 더 실을 수 있는지를 확인해야 한다는 것

2. 도착 마을을 기준으로 택배 정보를 정렬한다면 이후의 선택에 영향을 미치지 않는다는 것

 

위 요소들이 문제에서 어렵거나 헷갈릴 수 있는 점이라고 생각한다. 나는 1번은 헷갈렸고 2번은 어려웠다. 재밌다.