문제

8980번: 택배

풀이

사실 이 문제가 왜 그리디 알고리즘으로 해결이 가능한지 증명하지 못했습니다. 하지만 그럼에도 불구하고 할당받은 문제이기 때문에 풀이를 작성합니다.

이 문제를 [백준]1931번: 회의실 배정문제에 대입해 봅시다. 그렇다면 이 문제는 회의실이 C 만큼 있다고 할 수 있습니다. 보내는 마을은 회의 시작 시간, 받는 마을은 회의 끝나는 시간이라 할 수 있겠네요. 목적은 마찬가지로 가장 많은 회의를 배정하는 것입니다.

회의실이 많아졌지만 똑같습니다. 각 회의실에 가장 많은 회의를 배정하기 위한 최적의 해는 그리디 알고리즘으로 구할 수 있습니다. 회의가 끝나는 시간(받는 마을)이 시작 점과 가까운 순서대로 정렬한 후 그 순서대로 처리해주면 됩니다.

하지만 회의실이 많아졌다고 회의실 수 만큼 반복하기보단 다른 방법을 사용해 봅시다.

각 시간과 시간 사이에 남은 회의실 수를 저장합니다. 1~2 사이를 구간1, 2~3 사이를 구간2, ... 라고 한다면 초기의 구간별 남은 회의실 수는 구간1 = C, 구간2 = C, ... 가 됩니다.

예를 들어 C = 40, 1~2 시간 까지 10개의 회의실을 사용한다면 구간1 = 30이 됩니다.
추가로 1~3 시간동안 20개의 회의실을 사용한다면 구간1 = 10, 구간2 = 20이 됩니다.

그렇다면 1~4시간동안 30개의 회의실을 사용하려 한다면? 구간1, 구간2, 구간3 모두 30 이상이어야 하는데 구간1과 구간2의 남은 회의실이 모잘라 30을 모두 할당할 수 없습니다. 따라서 최소값인 구간1의 남은 10만큼만 할당할 수 있고 10개의 회의실을 사용하게 된다면 구간1 = 0, 구간2 = 10, 구간3 = 30이 됩니다.
마찬가지로 2~4 시간에 20개의 회의실이 필요해도 구간2와 구간3의 최소값 만큼만 할당할 수 있습니다.

구현은 방금 설명한 것처럼 구간마다의 남은 회의실을 고려하여 회의실 배정을 해야합니다.
그렇다면 가장 많은 회의실을 사용하기 위해 끝나는 시간으로 정렬한 순서대로 하나씩 처리하면 가장 많은 회의실을 배정할 수 있게 되겠네요.

회의실 배정 문제로 대입해서 풀었지만
회의 시작 시간 : 보내는 마을
회의 끝나는 시간 : 받는 마을
회의 개수 : 박스 개수
로 바꾸어 이번 문제를 해결할 수 있습니다.

코드

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

struct Delivery
{
    int from;
    int to;
    int box;

    bool operator<(Delivery input)
    {
        if (this->to == input.to)
            return this->from < input.from;
        else
            return this->to < input.to;
    }
};

int main ()
{
    cin.tie(0);
    ios_base::sync_with_stdio(false);

    int n, m, capacity;

    cin >> n >> capacity;
    cin >> m;

    vector<int> sizes(n+1, capacity);
    vector<Delivery> delivery(m);

    for (int i=0; i<m; ++i)
    {
        int a, b, c;
        cin >> a >> b >> c;
        delivery[i] = {a, b, c};
    }
    sort(delivery.begin(), delivery.end());

    int answer = 0;
    for (auto del : delivery)
    {
        int minSize = INT32_MAX; // 각 마을 중 가장 용량이 적게남은 
        for (int i=del.from; i<del.to; ++i)
            minSize = min(minSize, sizes[i]);

        int curBox = min(minSize, del.box);
        for (int i=del.from; i<del.to; ++i)
            sizes[i] -= curBox;
            
        answer += curBox;
    }

    cout << answer << endl;
}

문제의 예제2를 보면 2 5 70, 3 4 40이 주어집니다. 위에서 언급했듯이 도착 마을 순서로 정렬하게 되면 3 4 40 박스를 먼저 싣고 2 5 70 박스를 나중에 싣게 됩니다. 트럭은 최대 60까지만 싣을 수 있으니 2 5 20이 되겠네요. 어짜피 5번 마을까지 가는데 60까지만 배송이 가능합니다. 3 4 40 + 2 5 20 == 2 5 60입니다.

참고

https://www.acmicpc.net/board/view/125942