[백준][BOJ-8980][JAVA] 택배

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

8980번: 택배

import java.io.*;
import java.util.*;

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		StringTokenizer st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());

		int T = Integer.parseInt(br.readLine());
		List<Delivery> list = new ArrayList<>();

		for (int i = 0; i < T; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			int box = Integer.parseInt(st.nextToken());
			
			list.add(new Delivery(a, b, box));
		}
		
		Collections.sort(list);
		int[] weight = new int[N+1];
		Arrays.fill(weight, C);
		int result = 0;
		
		for (int i = 0; i < list.size(); i++) {
            Delivery d = list.get(i);
            int maxBoxNum = Integer.MAX_VALUE;
 
            for (int j = d.start; j < d.end; j++) {
                maxBoxNum = Math.min(maxBoxNum, weight[j]);
            }
 
            if (maxBoxNum >= d.boxCnt) {
                loadBox(weight, d.start, d.end, d.boxCnt);
                result += d.boxCnt;
            } else {
                loadBox(weight, d.start, d.end, maxBoxNum);
                result += maxBoxNum;
            }
        }
		
		System.out.println(result);
	}

	private static void loadBox(int[] weight, int start, int end, int num) {
		for (int j = start; j < end; j++) {
            weight[j] -= num;
        }
	}
}

class Delivery implements Comparable<Delivery>{
	int start;
	int end;
	int boxCnt;
	public Delivery(int start, int end, int boxCnt) {
		super();
		this.start = start;
		this.end = end;
		this.boxCnt = boxCnt;
	}
	@Override
	public int compareTo(Delivery o) {
		if(this.end == o.end) return this.start - o.start;
		return this.end - o.end;
	}
}

정리

이번 문제의 핵심은 도착 도시에 많은 박스를 내려주는 겁니다. 따라서 도착 도시를 기준으로 오름차순을 정렬하고 도착 도시가 같다면 시작 도시를 기준으로 오름차순을 정렬한 값으로 문제를 풉니다.

1. 도착 도시 기준 오름차순 정렬, 같은 경우 시작 시간으로 오름차순 정렬
2. 각 마을의 택배 최대 개수로 초기화
3. 택배 정보를 반복문 돌린다.
4. 택배의 정보 중 보내는 마을과 받는 마을을 보고, 각 마을 당 실을 수 있는 최대한도를 구한다.
5. 최대한도와 택배의 정보 중에 택배의 개수를 비교한다.
6. 최대한도가 택배의 개수보다 크다면 경로에 해당하는 마을의 택배 가능 개수를 빼준다.
7. 반대로 작다면 최대한도를 뺀다.