[백준] 8980 택배 (C++)

링크: https://www.acmicpc.net/problem/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이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 박스를 받는 마을번호는 보내는 마을번호보다 크다. 

출력

트럭 한 대로 배송할 수 있는 최대 박스 수를 한 줄에 출력한다.

---

풀이

회의실 배정과 비슷하지만 '박스 개수'라는 개념이 있어 조금 더 까다로운 문제이다.

정말 다행인 점은, 박스가 30개 있고 트럭에 20의 공간이 있을 때 일부인 20개만 실을 수 있다는 것이다.

(만약 일부를 싣지 못하고 공간이 30 이상일때만 실을 수 있었다면... 모든 경우의 수를 조사해야 할 듯?)

그렇기 때문에, 박스를 정렬하여 그리디로 접근하면 문제를 풀 수 있다.

 

먼저 박스에는 보내는 마을, 받는 마을, 개수 총 3가지 정보가 있다.

이 박스들을 받는 마을이 작은 순, 받는 마을이 같다면 보내는 마을이 작은 순으로 정렬해준다.

개수는 앞서 말했듯 트럭의 남은 공간에 관계없이 일부만 실을 수 있기 때문에 여기서는 큰 관계가 없다.

예제 입력 2를 정렬하면 다음과 같이 될 것이다.

 

그리고 트럭은 각 마을을 지날 때마다 실고 있는 박스의 개수가 다를 것이고, 남은 공간도 다를 것이다.

정렬한 순서대로 위에서부터 채워나가보자.

 

먼저 (1, 2, 30)에 해당되는 박스들을 싣는다. 1번 마을에서 트럭의 공간은 60이므로 문제 없이 실을 수 있고, 2번 마을에서 박스들을 내릴 것이므로 1번 마을에만 30을 추가해주면 된다.

 

이어서 (3, 4, 40)에 해당되는 박스들을 싣는다. 마찬가지로 3번 마을에서 트럭의 공간은 60이므로 40개의 박스들을 모두 문제 없이 실을 수 있다.

 

이어서 (2, 5, 70)에 해당되는 박스들을 싣는다. 그런데 3번 마을을 지나갈 때 이미 30만큼의 박스를 싣고 있고 남은 공간은 20이라는 것을 확인할 수 있다. 따라서 이 박스는 최대 20까지 실을 수 있다. 2~4번 마을에 20을 추가해준다.

 

이어서 (1, 6, 40)에 해당되는 박스들을 싣는다. 이미 3번 마을에 60만큼의 박스를 싣고 있어 남은 공간이 없고, 여기서는 박스를 실을 수 없다.

 

마지막으로 (5, 6, 60)에 해당되는 박스들을 싣는다. 5번 마을을 지나갈 때 싣고 있는 박스는 없고, 60개의 박스들을 모두 실을 수 있다. 따라서 60을 추가해준다.

 

최종적으로, 트럭 한 대로 배송할 수 있는 최대 박스 수는 30+40+20+0+60 = 150이다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

struct box{
    int beginTown;
    int endTown;
    int amount;
    box(int b, int e, int a): beginTown(b), endTown(e), amount(a) {}
};

bool compareBox(box b1, box b2){
    // 받는 마을번호가 작을수록 우선순위 높음
    if (b1.endTown != b2.endTown){
        return b1.endTown < b2.endTown;
    }
    // 받는 마을번호가 같다면 보내는 마을번호가 작은 순서
    return b1.beginTown < b2.beginTown;
}

// 마을을 지나갈 때 트럭 안에 들어갈 수 있는 박스 수
int townTruckBoxes[2001];
void init(int n, int c){
    for (int i = 1; i <= n; i++){
        townTruckBoxes[i] = c;
    }
}

int main(){
    int n, c, m;
    cin >> n >> c;
    cin >> m;

    vector<box> boxes;
    for (int i = 0; i < m; i++){
        int a, b, c;
        cin >> a >> b >> c;
        boxes.push_back(box(a, b, c));
    }

    // 박스들을 정렬
    sort(boxes.begin(), boxes.end(), compareBox);

    init(n, c);

    int answer = 0;
    for (int i = 0; i < m; i++){
        int minBoxes = boxes[i].amount;
        // 각 마을을 지나갈 때 트럭에 들어있는 박스양을 조사
        for (int j = boxes[i].beginTown; j < boxes[i].endTown; j++){
            minBoxes = min(minBoxes, townTruckBoxes[j]);
        }
        // 조사한 박스양만큼을 반영
        answer += minBoxes;
        for (int j = boxes[i].beginTown; j < boxes[i].endTown; j++){
            townTruckBoxes[j] -= minBoxes;
        }
    }

    cout << answer;
}