[BOJ] 8980번 : 택배

문제 링크 : 백준 8980번

[문제 접근]

dp문제인줄 알았는데 그리디로 풀 수 있을 것 같아서 그리디로 풀었다.

처음에는 최대한 최대 용량에 가득 채우면서 가능한 여러 곳에 내리게 하는 방식으로 접근했다. 즉, 마을 당 박스 수를 오름차순으로 정렬 후 최대 용량까지 채우는 방법이다.
하지만 반례로
1 4 40
2 3 10
3 4 40
이면 2->3->4 가 더 best가 된다.

그래서 다른 방법으로 보내는 마을과 받는 마을이 가까울수록 많이 배송할 수 있을 것 같아서 받은 마을을 오름차순으로 정렬한 후 보내는 마을 -> 받는 마을 사이에 있는 마을에 대해서 박스 계산을 해주었다.

ex)
1 2 10
1 3 20
2 3 10
3 4 20
1 4 30
2 4 20

1 2 10 일 때
마을 : 1 / 2 / 3 / 4
트럭 : 0+10 / 0 / 0 / 0
ans = 0 + 10 = 10

1 3 20 일 때
마을 : 1 / 2 / 3 / 4
트럭 : 10+20 / 0+20 / 0 / 0
ans = 10 + 20 = 30

2 3 10 일 때
마을 : 1 / 2 / 3 / 4
트럭 : 30 / 20+10 / 0 / 0
ans = 30 + 10 = 40

3 4 20 일 때
마을 : 1 / 2 / 3 / 4
트럭 : 30 / 30 / 0+20 / 0
ans = 40 + 20 = 60

이런식으로 각 마을당 넣을 수 있는 트럭 용량 수를 계산해주었다.
최대 용량을 넘길 때는 트럭 용량 수 중 최대값에서 넣을 수 있는 최대한의 박스를 각 마을에 넣어주면 된다.

1 4 30 일 때 최대값이 30 이므로 넣을 수 있는 최대한의 박스인 10을 더해준다.
마을 : 1 / 2 / 3 / 4
트럭 : 30+10 / 30+10 / 20+10 / 0
ans = 60 + 10 = 70

2 4 20 일 때
마을 : 1 / 2 / 3 / 4
트럭 : 40+0 / 40+0 / 30+0 / 0
ans = 70 + 0

ans = 70이 나오게 된다.

시간복잡도 : O(M*logM)

[소스 코드]

#include <iostream>
#include <algorithm>

using namespace std;
int n,ts,m;
int ans;
typedef pair<pair<int, int>, int> p;

bool cmp(p a, p b) {
    return a.first.second < b.first.second;
}

int main() {
    cin >> n >> ts >> m;
    vector<p> arr;
    vector<int> truck(n);

    for(int i=0 ; i<m ; i++) {
        int a,b,c;
        cin >> a >> b >> c;
        arr.push_back(p(make_pair(a, b), c));
    }
    sort(arr.begin(), arr.end(), cmp);
    
    int size = arr.size();
    for(int i=0 ; i<size ; i++) {
        int start = arr[i].first.first-1;
        int end = arr[i].first.second-1;
        int box = arr[i].second;
        int temp=0;
        int cnt=0;

        for(int j=start ; j<end ; j++) {
            temp = max(temp, truck[j]); // 해당하는 마을에서 쌓인 박스 수 중 가장 큰 수
        }
        if(temp+box<=ts) cnt = box; // 가장 큰 수에 박스를 넣어도 용량을 안넘으면
        else cnt = ts-temp; // 용량을 넘으면

        for(int j=start ; j<end ; j++) {
            truck[j] += cnt;
        }
        ans += cnt;
    }

    cout << ans << "\n";

    return 0;
}