[BOJ/백준][Gold4] 8980 : 택배 (C++)

www.acmicpc.net/problem/8980  

8980번: 택배

 

[난이도] Gold4

[유형] Greedy

 

[풀이]

어떤 마을에 도착했을 때 트럭에 실려있으면서 그마을이 목적지로 되어있는 택배는 모두 내리면 되므로

실을 때 어떻게 실어야 최적이 되는지만 생각하면 된다.

=> Greedy

=> 가장 빨리 내릴 수 있는 택배를 가장 많이 싣고 있는 것이 최적이다.

 

1. 각 마을에서 택배를 실을 때, 현재 택배를 실고있는 마을에서 가장 가까운 마을부터 택배를 싣는다.

   ex) 현재 마을이 i라면 목적지가 i+1 ~ N 순서로 택배를 차례로 싣는다.

 

2. 만약 i+1,i+2...j-1 번 마을이 도착지인 택배는 다실었는데 j번째를 싣다가 C를 초과하게 되면

   현재 최적이 되는 것을 방해하고 있는 택배들이 있는지 확인하고 그 택배들을 빼고 대신 j를 실어야 한다.

   제일먼저 빼야하는 택배(가장 비효율적인 택배) 들은 N 마을이 도착지인 택배들이다.

   => N~j+1 마을이 도착지인 택배들을 순서대로 확인하면서 있으면 그 택배들을 빼주고 j번 택배를 싣는다.

 

#include <cstdio>
#include <cstring>
int N,C,M,dest[2001][2001],cnt[2001],ans;
int main(){
    scanf("%d%d%d",&N,&C,&M);
    while(M--){
        int a,b,c;
        scanf("%d%d%d",&a,&b,&c);
        dest[a][b]=c;
    }
    int t = 0;
    for(int i=1;i<=N;i++){
        ans+=cnt[i];
        t-=cnt[i];
        for(int j=i+1;j<=N;j++){
            if(!dest[i][j]) continue;
            if(t+dest[i][j]<=C){
               cnt[j]+=dest[i][j];
               t+=dest[i][j];
            }else{
               cnt[j]+=C-t; 
               dest[i][j]-=C-t;
               t = C;               
               for(int k=N;k>j;k--){
                   if(!dest[i][j]) break;
                   if(cnt[k] > 0){
                       if(dest[i][j]<=cnt[k]){
                           cnt[j]+=dest[i][j];
                           cnt[k]-=dest[i][j];
                           dest[i][j]=0;
                       }else{
                           cnt[j]+=cnt[k];
                           dest[i][j]-=cnt[k];
                           cnt[k]=0;
                       }
                   }
               }
            }
        }
    }
    printf("%d",ans);
}

 

https://github.com/has2/Problem-Solving/blob/master/boj-solved.ac/Gold4/8980.cpp