[BaekJoon] 8980 택배 (Java)

1.  문제 링크

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

2.  문제

요약

• 직선 도로상에 왼쪽부터 오른쪽으로 1번부터 차례대로 번호가 붙여진 마을들이 있습니다.
• 마을에 있는 물건을 배송하기 위한 트럭 한 대가 있고, 트럭이 있는 본부는 1번 마을 왼쪽에 있으며, 트럭은 본부에서 출발하여 1번 마을부터 마지막 마을까지 오른쪽으로 가면서 마을에 있는 물건을 배송합니다.
• 각 마을은 배송할 물건들을 박스에 넣어 보내며, 본부에서는 박스를 보내는 마을번호, 박스를 받는 마을번호와 보낼 박스의 개수를 알고 있습니다.
• 트럭에 최대로 실을 수 있는 박스의 개수가 제한되어 있고, 트럭 한 대를 이용하여 다음의 조건을 모두 만족하며 최대한 많은 박스들을 배송하려고 합니다.
  • 조건 1 : 박스를 트럭에 실으면, 이 박스는 받는 마을에서만 내립니다.
  • 조건 2 : 트럭은 지나온 마을로 되돌아가지 않습니다.
  • 조건 3 : 박스들 중 일부만 배송할 수도 있습니다.
• 받는 마을번호는 보내는 마을번호보다 항상 큽니다.
• 마을의 개수, 트럭의 용량, 박스 정보(보내는 마을번호, 받는 마을번호, 박스 개수)가 주어질 때, 트럭 한 대로 배송할 수 있는 최대 박스 수를 구하는 문제입니다.
• 입력: 첫 번째 줄에 2보다 크거나 같고 2,000보다 작거나 같은 정수인 마을 수 N과 1보다 크거나 같고 10,000보다 작거나 같은 정수인 트럭의 용량 C가 주어지고 두 번째 줄에 1보다 크거나 같고 10,000보다 작거나 같은 정수인 박스 정보의 개수 M이 주어집니다. 세 번째 줄부터 M개의 줄에 박스를 보내는 마을번호, 박스를 받는 마을번호, 보내는 박스 개수(1 이상 10,000 이하의 정수)를 나타내는 양의 정수가 주어집니다. 박스를 받는 마을번호는 보내는 마을번호보다 큽니다.
• 출력: 첫 번째 줄에 트럭 한 대로 배송할 수 있는 최대 박스 수를 출력합니다.

3.  소스코드

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

public class Main {
    static int N, C, M;
    static Stuff[] stuffs;

    static void input() {
        Reader scanner = new Reader();

        N = scanner.nextInt();
        C = scanner.nextInt();
        M = scanner.nextInt();
        stuffs = new Stuff[M];

        for(int idx = 0; idx < M; idx++) {
            int sentTown = scanner.nextInt();
            int receivedTown = scanner.nextInt();
            int boxNum = scanner.nextInt();

            stuffs[idx] = new Stuff(sentTown, receivedTown, boxNum);
        }
    }

    static void solution() {
        Arrays.sort(stuffs);

        // 각 마을당 보낼 수 있는 최대 용량을 설정
        int[] weight = new int[N + 1];
        Arrays.fill(weight, C);

        int answer = 0;
        for(int idx = 0; idx < M; idx++) {
            Stuff stuff = stuffs[idx];
            int maxBoxNum = Integer.MAX_VALUE;

            // 보내는 마을과 받는 마을 사이의 경로 마을 중에서 보낼 수 있는 최대 한도를 구한다.
            for(int town = stuff.sentTown; town < stuff.receivedTown; town++) {
                maxBoxNum = Math.min(maxBoxNum, weight[town]);
            }

            // 위에서 구한 보낼 수 있는 최대 한도가 현재 보내려는 택배의 개수보다 크다면,
            // 보내는 마을과 받는 마을 사이의 경로 마을 모두 용량에서 현재 보내려는 택배의 개수를 뺀다.
            if(maxBoxNum >= stuff.boxNum) {
                for(int town = stuff.sentTown; town < stuff.receivedTown; town++) {
                    weight[town] -= stuff.boxNum;
                }
                answer += stuff.boxNum;
            } else {
                // 보낼 수 있는 최대 한도보다 현재 보내려는 택배의 개수가 클 경우,
                // 현재 보내려는 택배의 개수가 아닌 위에서 구한 최대 한도를 기준으로 한다.
                for(int town = stuff.sentTown; town < stuff.receivedTown; town++) {
                    weight[town] -= maxBoxNum;
                }
                answer += maxBoxNum;
            }
        }

        System.out.println(answer);
    }

    static class Stuff implements Comparable<Stuff> {
        int sentTown, receivedTown, boxNum;

        public Stuff(int sentTown, int receivedTown, int boxNum) {
            this.sentTown = sentTown;
            this.receivedTown = receivedTown;
            this.boxNum = boxNum;
        }

        @Override
        public int compareTo(Stuff s) {
            return this.receivedTown - s.receivedTown;
        }
    }

    public static void main(String[] args) {
        input();
        solution();
    }

    static class Reader {
        BufferedReader br;
        StringTokenizer st;

        public Reader() {
            br = new BufferedReader(new InputStreamReader(System.in));
        }

        String next() {
            while(st == null || !st.hasMoreElements()) {
                try {
                    st = new StringTokenizer(br.readLine());
                } catch (IOException e) {
                    e.printStackTrace();
                }
            }

            return st.nextToken();
        }

        int nextInt() {
            return Integer.parseInt(next());
        }
    }
}

4.  접근

• 각 마을당 해당 마을로 보낼 수 있는 최대 용량을 설정한 후에 이를 이용하여 배송할 수 있는 최대 박스 수를 구합니다.
• weight라는 배열을 생성하고 해당 배열의 값을 모두 트럭의 용량 C로 초기화시킵니다.
• 주어진 보낼 택배들을 받는 마을의 오름차순으로 정렬합니다.
  • 보내는 마을 기준으로 오름차순으로 정렬한다면, 만약 처음 보내는 마을에서 C만큼의 택배를 마지막 마을까지 보내야했을 때 트럭은 C만큼의 택배를 실은 후에 중간에 어느 마을에서도 택배를 실지 않고, 택배를 전달하지 않고 마지막 마을까지 가게 됩니다.
  • 그러면 중간에 있는 박스들을 모두 이동시키지 못하기 때문에 최대로 보내는 경우가 아닐 수 있습니다.
  • 택배를 보내는 것을 보내는 마을부터 받는 마을까지의 구간으로 생각해본다면, 앞에서부터 최소의 구간으로 박스를 가지고 이동시키는 것이 트럭에 공간이 여러 번 비워져 여러 구간으로 박스들을 이동시킬 수 있기 때문에 받는 마을 기준 오름차순으로 정렬합니다.
• 주어진 택배들을 순회하면서 배송할 수 있는 최대 박스 수를 구합니다.
  • 현재 택배에 대해 보내는 마을과 받는 마을 사이에 보낼 수 있는 최대 한도를 구합니다.
    • 보내는 마을부터 받는 마을 전까지 weight 값을 비교하여 그 중 가장 작은 값을 구합니다.
    • 만약 보낼 수 있는 최대 한도가 현재 보내려는 택배의 박스 개수보다 크거나 같다면 보내는 마을부터 받는 마을 전까지의 weight 값에서 보내려는 택배의 박스 개수만큼 빼주고 배송할 수 있는 최대 박스 수를 나타내는 answer 변수에 보내려는 택배의 박스 개수만큼 더해줍니다.
  • 만약 보낼 수 있는 최대 한도가 현재 보내려는 택배의 박스 개수보다 작다면 보내는 마을부터 받는 마을 전까지의 weight 값에서 보낼 수 있는 최대 한도만큼 빼주고 배송할 수 있는 최대 박스 수를 나타내는 answer 변수에 보낼 수 있는 최대 한도를 더해줍니다.
• 이렇게 구한 answer 값이 답이 됩니다.