[BOJ] 백준 8980번 : 택배 (JAVA)

문제의 링크 : https://www.acmicpc.net/problem/8980

8980번: 택배

문제

아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽으로 1번부터 차례대로 번호가 붙여진 마을들이 있다. 마을에 있는 물건을 배송하기 위한 트럭 한 대가 있고, 트럭이 있는 본부는 1번 마을 왼쪽에 있다. 이 트럭은 본부에서 출발하여 1번 마을부터 마지막 마을까지 오른쪽으로 가면서 마을에 있는 물건을 배송한다. 

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

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

마을의 개수, 트럭의 용량, 박스 정보(보내는 마을 번호, 받는 마을번호, 박스 개수)가 주어질 때, 트럭 한 대로 배송할 수 있는 최대 박스 수를 구하는 프로그램을 작성하시오. 단, 받는 마을번호는 보내는 마을번호보다 항상 크다.

예를 들어, 트럭 용량이 40이고 보내는 박스들이 다음 표와 같다고 하자.

보내는 마을받는 마을박스 개수

1	2	10
1	3	20
1	4	30
2	3	10
2	4	20
3	4	20

이들 박스에 대하여 다음과 같이 배송하는 방법을 고려해 보자.

(1) 1번 마을에 도착하면

다음과 같이 박스들을 트럭에 싣는다. (1번 마을에서 4번 마을로 보내는 박스는 30개 중 10개를 싣는다.)

보내는 마을받는 마을박스 개수

1	2	10
1	3	20
1	4	10

(2) 2번 마을에 도착하면

트럭에 실려진 박스들 중 받는 마을번호가 2인 박스 10개를 내려 배송한다. (이때 트럭에 남아있는 박스는 30개가 된다.)

그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 40개가 된다.)

보내는 마을받는 마을박스 개수

2

3

10

(3) 3번 마을에 도착하면 

트럭에 실려진 박스들 중 받는 마을번호가 3인 박스 30개를 내려 배송한다. (이때 트럭에 남아있는 박스는 10개가 된다.)

그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 30개가 된다.)

보내는 마을받는 마을박스 개수

3

4

20

(4) 4번 마을에 도착하면 

받는 마을번호가 4인 박스 30개를 내려 배송한다

위와 같이 배송하면 배송한 전체 박스는 70개이다. 이는 배송할 수 있는 최대 박스 개수이다.

입력

입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이상 10,000이하 정수이다. 다음 M개의 각 줄에 박스를 보내는 마을번호, 박스를 받는 마을번호, 보내는 박스 개수(1이상 10,000이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 박스를 받는 마을번호는 보내는 마을번호보다 크다. 

 

풀이

전형적인 그리디 알고리즘 문제였습니다. 저는 처음에 보내는 마을을 기준으로 정렬을 해서 풀어보았으나, 역시 반례가 존재하였습니다. 아래 예시와 같이 말이죠.

 

최대 용량 40

보내는 마을	받는 마을	택배의 개수
1	4	40
2	3	20
3	4	30

 

무조건 시작점을 기준으로 하면, 위와 같이 먼 거리를 이동하는데 용량까지 최대로 차지할 경우, 다음 마을에 대해서는 택배를 더 실을 수가 없습니다.

따라서, 도착점을 기준으로 오름차순 정렬하되, 도착점이 같을 경우 시작점을 오름차순 정렬하는 것이 핵심이었습니다.

또, 정렬한 배열을 보면서 차례대로 택배를 실고, 내리고 하는 데는 어려움이 있습니다. 아래 예시를 봅시다.

 

최대 용량 : 40

보내는 마을	받는 마을	택배의 개수
1	2	10
1	3	20
2	3	10
1	4	30

 

1->2에서 10, 1->3에서 20을 싣는 것은 문제가 되지 않습니다. 다만, 2->3에서 택배를 싣는 것은 문제가 있습니다.

원래 택배는 1번 마을, 2번 마을,... 차례로 해서 택배를 싣고 내립니다. 하지만, 위는 1번 마을, 2번 마을, 1번 마을 순으로 뒤죽박죽이기때문에 전후 관계를 파악하기가 어렵습니다.

따라서, 순서대로 택배를 싣고 내리면서 로직을 세우는 것이 아니라, 미리 각 마을마다 최대 용량을 설정해 둔 다음, 그 용량에서 택배의 개수만큼 순차적으로 빼는 방식이 적합합니다.

결론적으로, 전반적인 로직은 아래와 같습니다.

1. 택배의 정보를 받는 마을을 기준으로 오름차순 정렬, 받는 마을이 같은 경우 보내는 마을을 기준으로 오름차순 정렬한다.

2. 각 마을 당 보낼 수 있는 택배의 최대 개수(C)를 설정한다.

3. 택배의 정보에 대한 반복문을 실행한다.

3-1. 택배의 정보 중 보내는 마을과 받는 마을을 보고, [보내는 마을, 받는 마을) 경로 중 각 마을 당 실을 수 있는 최대 한도(maxBoxNum)를 구한다.

3-2. maxBoxNum와 현재 택배의 정보 중 택배의 개수(boxNum)를 비교한다.

3-2-1. maxBoxNum가 boxNum보다 크다면, [보내는 마을, 받는 마을) 경로에 해당하는 마을의 C에서 boxNum을 뺀다.

3-2-2. maxBoxNum가 boxNum보다 작다면, [보내는 마을, 받는 마을) 경로에 해당하는 마을의 C에서 maxBoxNum을 뺀다.

 

아래 예제를 보면서, 위 로직을 이해해보도록 합시다.

 

예제

최대 용량 : 40

보내는 마을	받는 마을	택배의 개수
1	2	10
1	3	20
2	3	10
1	4	30
2	4	20
3	4	20

위와 같이 받는 마을을 기준으로 오름차순 정렬을 합니다.

 

그리고, 마을 당 택배를 보낼 수 있는 최대 용량은 문제에서 제시된 40으로 설정합니다. 마을의 개수는 4개인데 마을의 번호는 3까지만 고려하는 이유는 어차피 4번 택배에서는 택배를 실지 않기 때문입니다.

마을의 번호	1	2	3
최대 용량	40	40	40

 

이제, 첫 번째 표를 보면서 해답(ans)을 구해봅시다.

보내는 마을이 1, 받는 마을이 2이므로 1번 마을의 최대 용량(40)에서 10을 뺍니다. 따라서 ans = 10이고, 마을의 상태는 아래와 같이 바뀝니다.

마을의 번호	1	2	3
최대 용량	30	40	40

 

보내는 마을이 1, 받는 마을이 3이므로 1번 마을과 2번 마을 중 가능한 최대 용량(30)에서 각각 20을 뺍니다. ans = 30.

마을의 번호	1	2	3
최대 용량	10	20	40

 

보내는 마을이 2, 받는 마을이 3이므로 2번 마을의 최대 용량(20)에서 10을 뺍니다. ans = 40.

마을의 번호	1	2	3
최대 용량	10	10	40

 

보내는 마을이 1, 받는 마을이 4이므로 1~3번 마을의 최대 용량(10)에서 30을 빼려고 했더니, 음수가 나와버립니다. 따라서, 이 경우에는 1~3번 마을에 대해 30을 빼는 것이 아닌, 10을 빼 주어야 합니다. ans = 50.

마을의 번호	1	2	3
최대 용량	0	0	30

 

보내는 마을이 2, 받는 마을이 3이므로 2번 마을의 최대 용량(0)에서 20을 빼려고 했더니, 음수가 나와버립니다. 이 경우에는 각 마을에 0을 빼어도 별 차이가 없으니 패스합니다. ans = 50.

마을의 번호	1	2	3
최대 용량	0	0	30

 

보내는 마을이 3, 받는 마을이 4이므로 3번 마을의 최대 용량(30)에서 20을 뺍니다. ans = 70

마을의 번호	1	2	3
최대 용량	0	0	10

 

그리고 더 이상 택배의 정보는 없으므로 위 과정을 종료합니다. 결과적으로 답이 70임을 알 수 있습니다.

 

추가 사항1

저는 위와 같이 받는 마을을 기준으로 정렬을 하였지만, 제 친구는 이동 거리가 짧은 순으로 정렬을 했다가 틀렸다고 합니다. 저도 반례를 찾지 못해서 한참 고민하다가, 아래와 같은 반례를 찾을 수 있었습니다. 혹시나 이동 거리를 기준으로 정렬하신 분은 아래 표를 참고하시길 바랍니다. 로직은 위 방식(각 마을의 용량에서 택배의 개수를 뺌)을 따릅니다.

보내는 마을	받는 마을	택배의 개수
3	5	100
1	4	100
4	7	100

 

3->5로 가는 경로에 100개씩 택배를 실게 되면 3, 4마을은 더 이상 택배를 실을 수 없게 됩니다. 따라서 1->4, 4->7 경로는 택배를 실을 수 없습니다.

하지만, 이동 거리가 아니고, 받는 마을을 기준으로 정렬해 봅시다.

보내는 마을	받는 마을	택배의 개수
1	4	100
3	5	100
4	7	100

 

1->4로 가는 경로에 100개, 4->7로 가는 경로에 100개로 총 200개의 택배를 실을 수 있습니다.

 

추가 사항2

그렇다면, 이렇게 3가지 기준 중에 2가지는 반례를 찾았지만, 왜 도착점이 빠른 순서가 최선일까요?

먼저 증명을 2줄로 해 보겠습니다.

1. n개의 구간에서 최대 m개의 짐을 한 번에 배송하는 것은 n개의 구간에서 1개의 짐을 m번 나눠서 배송하는 것과 같다.

2. n개의 구간을 서로다른 m개의 구간으로 나누는 최선의 수는 남은 구간이 최대가 될 때에 해당한다.

 

먼저, 첫 번째 줄은 이해가 금방 되실겁니다. 예를 들어, 우리가 10개의 택배를 배송하려고 하는데 10개를 한 번에 배송해도 되지만, 택배 1개씩 10번 운반하는 것도 가능합니다. (물론, 문제는 그것을 요구하지는 않았습니다.)

그리고 우리는 택배 1개씩 10번 운반하는 과정을 주의 깊게 볼 필요가 있습니다. 

아래 그림을 봅시다.

주황색 선은 택배가 이동할 수 있는 최대 경로이고, 파란색 선은 1->2, 1->3과 같은 각각의 택배가 이동하는 경로를 의미합니다. 위 선을 그대로 위로 옮겨 붙이면서, 어떻게 이어야 최선인지 판단해야합니다.

그리고 그것은 증명의 2번째 줄에서 알 수 있습니다. 바로, 남는 거리가 최대가 되어야한다는 것이죠. 이게 무슨 말이냐면, 문제에서 택배는 왼쪽에서 오른쪽으로 같은 곳을 또 방문하지 않고, 순차적으로 이동만 합니다. 즉, 1->3보다는 1->2 구간부터 수행하는 것이 나머지 남는 구간이 이득이 됩니다. 마찬가지로, 2->3 보다는 1->2를 먼저 방문하는 것이 남는 구간이 더 많다는 것입니다.

결론적으로, 위와 같은 이유로 '도착점'을 기준으로 택배를 배달하는 것이 최선의 수라고 판단할 수 있습니다.

 

아래는 위 과정을 정리한 소스코드입니다.

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;
 
class Delivery implements Comparable<Delivery> {
    int start; // 보내는 마을
    int end; // 받는 마을
    int boxNum; // 박스의 개수
 
    Delivery(int start, int end, int boxNum) {
        this.start = start;
        this.end = end;
        this.boxNum = boxNum;
    }
 
    @Override
    public int compareTo(Delivery arg0) {
        if (end == arg0.end) {
            return start - arg0.start;
        }
        return end - arg0.end;
    }
}
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
 
        int N = Integer.parseInt(st.nextToken()); // 마을의 수
        int C = Integer.parseInt(st.nextToken()); // 트럭의 용량
 
        int M = Integer.parseInt(br.readLine()); // 보낼 박스 정보의 개수
        Delivery[] deliveries = new Delivery[M + 1];
        for (int i = 1; i <= M; i++) {
            st = new StringTokenizer(br.readLine());
            int start = Integer.parseInt(st.nextToken());
            int end = Integer.parseInt(st.nextToken());
            int boxNum = Integer.parseInt(st.nextToken());
 
            deliveries[i] = new Delivery(start, end, boxNum);
        }
        // 택배를 받는 마을을 기준으로 오름차순 정렬을 하되, 받는 마을이 같을 경우
        // 보내는 마을을 기준으로 오름차순 정렬을 한다.
        Arrays.sort(deliveries, 1, M + 1);
 
        // 각 마을당 보낼 수 있는 최대 용량을 설정한다.
        int[] weight = new int[N + 1];
        for (int i = 1; i < N; i++) {
            weight[i] = C;
        }
 
        int ans = 0;
        for (int i = 1; i <= M; i++) {
            Delivery d = deliveries[i];
 
            int maxBoxNum = Integer.MAX_VALUE;
 
            // 보내는 마을과 받는 마을 사이의 경로 마을 중에서 보낼 수 있는 최대 한도를 구한다.
            for (int j = d.start; j < d.end; j++) {
                maxBoxNum = Math.min(maxBoxNum, weight[j]);
            }
 
            // 위에서 구한 보낼 수 있는 최대 한도가 현재 보내려는 택배의 개수보다 크다면,
            // 보내는 마을과 받는 마을 사이의 경로 마을 모두 용량에서 현재 보내려는 택배의 개수를 뺀다.
            if (maxBoxNum >= d.boxNum) {
                for (int j = d.start; j < d.end; j++) {
                    weight[j] -= d.boxNum;
                }
                ans += d.boxNum;
            } else {
                // 보낼 수 있는 최대 한도보다 현재 보내려는 택배의 개수가 클 경우,
                // 현재 보내려는 택배의 개수가 아닌 위에서 구한 최대 한도를 기준으로 한다.
                for (int j = d.start; j < d.end; j++) {
                    weight[j] -= maxBoxNum;
                }
                ans += maxBoxNum;
            }
        }
 
        bw.write(ans + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.