[백준] 8980. 택배 (Java)

 

문제

8980번: 택배

 

알고리즘

정렬, 그리디 알고리즘

 

 

풀이

택배를 받는 마을 번호을 기준으로 오름차순 정렬하면 항상 최적의 해를 보장한다.

현재 배송 가능한 택배 중 가장 가까운 마을에 배송할 수 있는 택배부터 담는게 가장 효율적이기 때문이다.

 

현재 담은 택배들의 정보를 바탕으로

각 마을을 지날 때 어느정도의 택배를 가지고있을 지 계산하여 다음 택배를 얼마나 담을지 계산한다.

 

다음은 예제 1을 [받는 마을 번호 기준 오름차순 정렬]한 것이다.

보내는 마을은 상관없기 때문에 일부러 역순으로 넣었다.

1. 첫번째 택배 ~ 네번째 택배

현재 담겨있는 택배가 없으므로 첫번째 박스를 담을 수 있다.

택배를 담고 나면 다음과 같이 1번 마을을 지날 때 담겨 있는 택배 무게가 10 증가한다.

네번째 택배까지 담고나면 

담겨있을 택배 무게 리스트는 다음과 같다.

 

2. 다섯번째 택배

다섯번째 택배는 2번 마을에서 시작하여 4번 마을까지 간다.

3번 마을은 담겨있을 택배 무게가 20이기 때문에 40-20 = 20의 여유가 있어 전부 담을 수 있지만

2번 마을에서 담겨있을 택배 무게가 30이기 때문에 10의 여유만 있다.

따라서 다섯번째 택배는 10만큼만 담는다.

 

3. 여섯번째 택배

여섯번째 택배는 1번 마을에서 시작하여 4번 마을까지 간다.

하지만 2번 마을에서 여유 무게가 0이기 때문에 여섯번째 택배는 담을 수 없다.

 

각 과정에서 택배를 담을 수 있는만큼 담으면서 해당 무게를 전부 합치면 정답을 구할 수 있다.

 

 

코드

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

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

		StringTokenizer st = new StringTokenizer(br.readLine(), " ");
		int N = Integer.parseInt(st.nextToken());
		int C = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(br.readLine());
		int used[] = new int[N];

		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(br.readLine(), " ");
			int start = Integer.parseInt(st.nextToken());
			int end = Integer.parseInt(st.nextToken());
			int value = Integer.parseInt(st.nextToken());

			boxList.add(new Box(start, end, value));
		}

		Collections.sort(boxList);

		int ans = 0;
		for (int i = 0; i < M; i++) {
			Box cur = boxList.get(i);

			// 배송 가능한 최대 용량 계산
			int max = check(cur, C, used);
			if (max > 0) {
				for (int j = cur.start; j < cur.end; j++) {
					used[j] += max;
				}
				ans += max;
			}
		}
		System.out.println(ans);
	}

	// 배송 가능한 용량 계산
	private static int check(Box cur, int c, int[] used) {

		int min = cur.value;
		for (int i = cur.start; i < cur.end; i++) {
			min = Math.min(min, c - used[i]);

			if (min == 0) break;
		}

		return min;
	}

	static class Box implements Comparable<Box> {
		int start, end, value;

		public Box(int start, int end, int value) {
			this.start = start;
			this.end = end;
			this.value = value;
		}

		@Override
		public int compareTo(Box o) {
			return end - o.end;
		}
	}
}