[Gold 1] 8980 택배

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

8980번: 택배

 

이 문제는 그리디 알고리즘을 사용해서 해결할 수 있다.

문제에서 각 박스의 정보가 입력으로 들어온다.

박스의 정보는 보내는 마을 번호, 받는 마을 번호, 박스의 개수가 있다.

입력으로 받기 위해 pair 자료형을 사용했다.

 

또한, 박스 정보를 도착 마을 순서로 정렬하여 탐색 시 가장 작은 도착 마을부터 할 수 있도록 하였다.

그 이유는 보내는 마을과 받는 마을이 가까울수록 많이 배송할 수 있다.

따라서 마을을 오름차순으로 정렬한 후 보내는 마을 -> 받는 마을 사이에 있는 마을에 대해서 박스 계산을 해주었다.

 

예시 입력으로 아래 값이 들어오면 

4 40
6
3 4 20
1 2 10
1 3 20
1 4 30
2 3 10
2 4 20

 

배열은 다음과 같이 정렬된다.

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

 

위 과정의 시간복잡도 는 O(M*logM)가 된다.

 

#include<iostream>
#include<algorithm>
using namespace std;
 
int N, C, M;
int result = 0;
vector<pair<pair<int, int>, int>> arr;
int dp[2001];


bool bigger(pair<pair<int, int>, int> a, pair<pair<int, int>, int> b){
    return a.first.second < b.first.second;
}
 
int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

    cin>>N>>C;

    cin>> M;

    int a, b, c;
    for(int i = 0;i<M;i++){
        cin>>a>>b>>c;
        arr.push_back({{a,b},c});
    }
    sort(arr.begin(),arr.end(), bigger);

    for(int i = 0;i<arr.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 counter = 0;

        for(int j = start; j < end; j++){
            temp = max(temp, dp[j]);
        }
        if(temp + box <= C) counter = box;
        else counter = C - temp;

        for(int j = start; j < end; j++)
            dp[j] += counter;
        
        result += counter;
    }
    cout<<result<<'\n';
}