[백준] 택배 8980 자바

풀이가 직관적이지만 생각해내기 쉽지 않은 상당히 어려운 문제라고 생각합니다.

우선순위 큐를 사용해서 풀이하였습니다.

 

가장 어렵다고 생각했던 부분중에 하나는 우선순위 큐의 우선순위가 도착지점(오름차순)으로 되어야만 풀이가

가능하다는 점이었습니다.

 

출발지점을 우선순위로 두고 각 마을에서 최대무게만큼 챙겨가는게 가장 이득이 아닐까 생각해서 그렇게 풀었었는데,

1번 마을에서 4번 마을(끝마을이라고 생각하면) 까지 상자무게가 40(최대무게라고 치면) 중간에 아무것도 챙겨갈 수가 없고 4번마을까지 냅다 운전만해야됩니다...ㅠ

 

때문에 도착지점이 가까운 순서로 박스를 싣는다고 생각하고, 도착지점이 같다면 출발지점(오름차순)으로 우선순위를 정하여 상자를 넣었습니다.

 

처음에 마을 배열을 선언하였고 각 마을마다 최대무게를 부여했습니다.

그리고 상자가 도착지점에 다다를 때까지 상자를 내려놓을 수 없다는 점을 생각해서,

도착지점까지 경유하는 마을은 상자무게만큼 빼주면서 계산했습니다.

 

말로는 이해하기 어려운 내용이라고 생각합니다.

 

steady-coding.tistory.com/58<- 사실 이 곳보다 더 잘 설명한 곳이 없습니다. 제 글과 코드를 보고 이해가 어려우시다면

링크를 통해서 쉽게 이해하실 수 있다고 생각합니다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class 택배 {

	static class tuple implements Comparable<tuple> {

		int start, end, weigh;

		tuple(int s, int e, int w) {
			this.start = s;
			this.end = e;
			this.weigh = w;
		}

		@Override
		public int compareTo(tuple o) {
			if (end == o.end) {
				return start - o.start;
			}

			return end - o.end;
		}
	}

	static PriorityQueue<tuple> pq = new PriorityQueue<tuple>();
	static int s, e, w, n, c, size, capa, des, start, res = 0;
	static int[] town;

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

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		n = Integer.parseInt(st.nextToken());
		c = Integer.parseInt(st.nextToken());
		town = new int[n+1];
		st = new StringTokenizer(br.readLine());

		size = Integer.parseInt(st.nextToken());

		for (int x = 0; x < size; x++) {
			st = new StringTokenizer(br.readLine());
			s = Integer.parseInt(st.nextToken());
			e = Integer.parseInt(st.nextToken());
			w = Integer.parseInt(st.nextToken());

			pq.add(new tuple(s, e, w));
		}
		
		for(int x=1; x<=n; x++) {
			town[x] = c;
		}

		while(!pq.isEmpty()) {
			tuple t = pq.poll();
			
			int capa = Integer.MAX_VALUE;
			s = t.start;
			e = t.end;
			w = t.weigh; //상자의 무게
			
			for(int x=s; x<=e; x++) {
				capa = Math.min(capa, town[x]); // 박스의 경로중에 가장 최대무게량이 적은 마을의 무게
			}
			
			if(w <= capa) // 상자를 고스란히 가져갈 수 있다면
			{
				for(int x=s;x<e;x++) { //무게 다 빼주고
					town[x] -= w;
				}
				res+=w;
			}else {
				for(int x=s;x<e;x++) { //아니라면 최소만큼만 빼주고(들고가고)
					town[x] -= capa;
				}
				res+=capa;
			}
			

		}
		System.out.println(res);
	}
}