[백준 8980] 택배 (JAVA)

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

8980번: 택배

 

처음에는 출발지점을 오름차순으로 해서 15점 밖에 못받았다..

다시 확인해보니, 도착지점이 한참 멀었는데 트럭에 실었을 경우에는 비효율적인 것으로 알게 되었다.

따라서 도착지점으로 오름차순 정렬하여 해결할 수 있었다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.StringTokenizer;

public class Main {

	static class Node implements Comparable<Node> {
		int start, end, w;

		Node(int start, int end, int w) {
			this.start = start;
			this.end = end;
			this.w = w;
		}

		@Override
		public int compareTo(Node n) {
			if (this.end == n.end)
				return this.start - this.start;
			return this.end - n.end;
		}

	}

	public static void main(String[] args) throws NumberFormatException, 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 m = Integer.parseInt(br.readLine());
		ArrayList<Node> list = new ArrayList<>();
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.readLine());
			int s = Integer.parseInt(st.nextToken());
			int e = Integer.parseInt(st.nextToken());
			int w = Integer.parseInt(st.nextToken());
			list.add(new Node(s, e, w));
		}

		Collections.sort(list);
		int result = 0;
		int[] capacities = new int[n + 1];
		Arrays.fill(capacities, c);

		for (int i = 0; i < m; i++) {
			Node node = list.get(i);
			int start = node.start;
			int end = node.end;
			int box = node.w;
			int capacity = Integer.MAX_VALUE;

			//트럭에 실고 가는 동안의 길 중에 수용할 수 있는 가장 작은 무게 찾기
			for (int j = start; j < end; j++) {
				capacity = Math.min(capacity, capacities[j]);
			}

			//위에서 찾은 무게와 박스 무게 비교하여 둘 중 작은 값을 
            // 실고 가는 길들에 마이너스~
			for (int j = start; j < end; j++) {
				capacities[j] -= Math.min(capacity, box);
			}
			result+=Math.min(capacity, box);
		}

		System.out.println(result);
	}

}