[백준] 8980번 택배 (C)

출처

2013 전국 본선 초등2

알고리즘

그리디

힌트

상자를 싣고 갈 구간을 보자.

 

문제 풀이

그리디 알고리즘으로 간단하게 풀리는 문제지만 뭐에 대해서 그리디를 적용시킬지 찾는게 쉽지 않다.

결론 부터 말하자면 상자가 트럭에 실려 있는 구간이 짧은 순으로 확인하면 된다. 구간이 같다면 먼저 실을 수 있는 상자를 선택한다. 따라서 상자를 목적지, 출발지 순으로 오름차순 정렬하면 된다.

그 뒤 반복문으로 앞에서 부터 살피면 되는데 이번에 선택된 상자(now)가 트럭에 실려있어야 할 구간을 살피고 모두 실을 수 있다면 now의 cost를, 용량이 초과된다면 남은 용량 만큼을 그 구간에 더해주면 된다.

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

#include<iostream> #include<algorithm>  using namespace std;   pair<int, int> pii;   typedef struct In{     int from,to,cost; }In;   In ins[10001];   // 목적지, 출발지 순으로 정렬  int cmp(In a, In b){         if(a.to!=b.to)         return a.to < b.to;     return a.from < b.from; }   int box[2001];        // 그 구간에서 트럭이 들고 있는 상자의     int main(){     int ans=0;     int n,c,m;     cin>>n>>c>>m;       for (int i=0; i < m; i++){          scanf("%d %d %d", &ins[i].from, &ins[i].to, &ins[i].cost);      }          sort(ins, ins + m , cmp);     for(int i=0;i<m;i++){           In now = ins[i]; // 이번에 볼 입력 값              int already = 0; // 주어진 구간에서의 최대 상자 수                  for (int i = now.from; i < now.to; i++)              already=max(already,box[i]);           // 상자의 최대 갯수를 넘길 수 있기 때문에          // 지금 보고 있는 상자의 개수와 남은 용량중 작은 것을 선택         int add = min(now.cost, c - already);                   for (int i = now.from; i < now.to; i++) { //구간에 추가              box[i] += add;          }               ans += add; // 추가한 만큼을 답에 더해줌      }          cout << ans << "\n";     return 0; }