[백준] 8980. 택배

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

8980번: 택배

이 문제는 그리디로 풀면 된다. 트럭에 실을 수 있는 택배의 총량이 c인데, c는 최대한 도착점이 가까운 택배들로 채워져야 한다. 그래야 금방 택배를 내리고 새로운 택배를 실을 수 있기 때문이다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer st;
    static int answer = 0;

    public static void main(String[] args) throws IOException {

        st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());
        List<List<Package>> list = new ArrayList<>();
        for (int i = 0; i <= n; i++) {
            list.add(new ArrayList<>());
        }

        int m = Integer.parseInt(br.readLine());
        for (int i = 0; i < m; i++) {
            st = new StringTokenizer(br.readLine());
            int from = Integer.parseInt(st.nextToken());
            int to = Integer.parseInt(st.nextToken());
            int cnt = Integer.parseInt(st.nextToken());
            list.get(from).add(new Package(to, cnt));
        }

        // 1~n까지 접근하며 택배 싣고 보내기
        int[] truck = new int[n + 1]; // 트럭에 담긴 택배 정보
        int sum = 0;

        for (int i = 1; i <= n; i++) {
            // 1. 택배 내리기
            answer += truck[i];
            sum -= truck[i];
            truck[i] = 0;

            // 2. 택배 싣기
            for (Package p : list.get(i)) {
                truck[p.to] += p.cnt;
                sum += p.cnt;
            }

            // 3. 트럭에 택배가 c 초과로 실린 경우, 도착지가 먼 택배를 우선으로 버리기
            if (sum <= c) continue;

            for (int j = n; j >= 0; j--) {
                if (truck[j] == 0) continue;
                // j로 가는 택배를 다 버려도 트럭에 실린 택배 총량이 c 이상인 경우, j로 가는 택배 다 버리기
                if (sum - truck[j] >= c) {
                    sum -= truck[j];
                    truck[j] = 0;
                }
                // j로 가는 택배를 다 버리면 트럭에 실린 택배 총량이 c 미만인 경우, 총량이 c가 되는 만큼만 버리기
                else {
                    truck[j] -= sum - c;
                    sum -= sum - c;
                    break;
                }
            }
            sum = c;
        }

        System.out.println(answer);
    }

    public static class Package {
        int to, cnt;

        public Package(int to, int cnt) {
            this.to = to;
            this.cnt = cnt;
        }
    }
}