[8980번] 택배

문제 출처 :

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

알고리즘 분석 :

문제 해결에 필요한 사항

1. 그리디 알고리즘

이 문제를 해결하기위해서 그리디 알고리즘을 이용한다.

이때 그리디 알고리즘을 어느 부분에 기준을 잡느냐에 따라 AC / WA가 나오게 되는데 필자는 처음에 보내는 박스의 개수를 기준으로 그리디를 진행했다가 WA를 받았다.

그리디를 어떻게 적용할까 생각하다보니, 최대한 가까운 곳에 많이 보낼 수록 트럭에 적재할 수 있는 내용물들이 많아진다는 것을 알아냈다.

결국 그리디는 다음과 같이 이용하면 AC를 받을 수 있다.

-> 최대한 가까운 곳에 많이 보낼 수 있도록 정렬을 하여 O(N*M)에 해결하라.

부가적인 내용은 주석을 통해 달아두었다.

소스 코드 : 

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58

#include <iostream> #include <cstdio> #include <algorithm>   using namespace std;   typedef pair<int, pair<int, int> > pii;   int truck[10002]; pii arr[10002];   int main() {     int n, c, m;     scanf("%d %d %d", &n, &c, &m);       for (int i = 0; i < m; i++)     {         int from, to, val;         scanf("%d %d %d", &from, &to, &val);           arr[i].first = to;         arr[i].second.first = from;         arr[i].second.second = val;     }       // to를 기준으로 정렬     sort(arr, arr + m);       long long ans = 0;       for (int i = 0; i < m; i++)     {         int get = 0;         int from = arr[i].second.first;         int to = arr[i].first;         int val = arr[i].second.second;           // 트럭이 적재하고 있는 최댓값을 구한다.         for (int j = from; j < to; j++)             get = max(get, truck[j]);           // 트럭에 실을 수 있는 최솟값을 구한다.         get = min(c - get, val);         ans += get;           // 트럭에 누적 적재 합을 더해준다.         for (int j = from; j < to; j++)             truck[j] += get;     }       printf("%lld", ans);       return 0; }   //                                                       This source code Copyright belongs to Crocus //                                                        If you want to see more? click here >>

Crocus