[백준] 택배

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

8980번: 택배

그리디 알고리즘을 이용하는 문제입니다.

 

우선 문제부터 간단하게 요약하면,

용량이 정해진 택배 트럭이 마을마다 물건을 배송합니다. 이 때, 보내는 마을, 받는 마을, 박스 개수가 주어질 때, 트럭 한대로 배송할 수 있는 최대 박스 수를 구하는 문제입니다.

 

<Solution>

greedy 알고리즘을 활용해야 하는 문제입니다. 

간단한 예시로 문제를 살펴봅시다. 

[INPUT]

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

이러한 input에 대해 그림을 그려 생각해봅시다. 

현재의 상황은 위의 그림과 같은 상황입니다. 

 

뭔가 greedy를 사용해야 할 것 같은 느낌이 드는데, greedy를 사용하려면, 정렬을 해야합니다. 

만약 출발지를 기준으로 정렬을 하면, 첫 출발지에서 실어서 가장 끝까지 가는 택배 상자를 실으면 굉장한 손해를 보기 떄문에, 출발지를 기준으로 sorting하는 것은 아닌 것을 알 수 있습니다.

 

그러면 도착지를 기준으로 sorting 해봅시다. 

 

도착지를 기준으로 sorting하면 다음과 같은 상황이 됩니다. 

잘 생각해보면, 도착지가 가장 가까운 애 부터 싣는게 좋은 것이라는 것을 알 수 있습니다. 

따라서 이 상황에서 greedy한 로직을 세워보면, 

1.마을에 도착하면, 해당하는 마을에 내리는 짐을 모두 내린다. 2. 도착지가 가장 가까운 애 부터 택배 차가 중간에 넘치지 않을 만큼 싣는다.

이 로직을 실제로 구현하면 되는 것을 알 수 있습니다. 

 

실제로 truck이라는 array를 만들어 만약 1번마을에서 2번마을로 가는 짐을 10개 싣는다면, 

truck [0][0][0][0][0][0][0]...

의 상태에서 

truck [0][10][0][0][0][0][0]...

로 바뀌고, 

 

여기에서 1번에서 3번 마을로 가는 짐을 20개 또 싣는다면, 

truck의 index 1, 2가 20을 더해서 용량 초과가 되는지 안되는지 확인하고 

truck [0][30][20][0][0][0][0]...

이런 형태로 바꿔 나가면 됩니다. 만약 짐을 30개 싣어야 하는데 10개밖에 못싣는다 하면, 10개를 싣도록 구현 하면 됩니다.

 

실제 구현은 아래와 같습니다.

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

int N, C, M;
// int S[10000+10];
// int E[10000+10];
// int NUM[10000+10];

struct INPUT{
    int S, E, NUM;
};
struct INPUT INPUT_[10000+10];
int truck[2000+10];


void InputData(){
    cin >> N >> C;
    cin >> M;
    for (int i=0; i<M; i++){
        // cin >> S[i] >> E[i] >> NUM[i];
        cin >> INPUT_[i].S >> INPUT_[i].E >> INPUT_[i].NUM;
    }

}
bool compare(struct INPUT a, struct INPUT b){
    return a.E < b.E;
}

int solve(){
    int return_val =0;
    // sort 
    sort(INPUT_, INPUT_+M, compare);
    for(int i = 0; i<M; i++){
        //check range
        int available_box_max = C;
        for(int j = INPUT_[i].S; j<INPUT_[i].E; j++){
            // check how many boxes available
            available_box_max = min(C-truck[j],available_box_max);
        }
        // fill boxes
        int tmp = (INPUT_[i].NUM > available_box_max)? available_box_max : INPUT_[i].NUM;
        for(int j = INPUT_[i].S; j<INPUT_[i].E; j++){
            
            truck[j]+= tmp;
        }
        return_val+= tmp;
    }
    return return_val;

}

int main(){
    int ans = -1;

    InputData();// 입력받는 부분

    // 여기서부터 작성
    ans = solve();

    cout << ans << endl;// 출력하는 부분
    return 0;
}