백준 - 택배 (8980) : JAVA

문제 유형
그리디, 정렬

풀이 방법 도출
문제의 조건은 다음과 같습니다.

1. 마을에 있는 물건을 배송하기 위한 트럭 한 대가 있고, 트럭이 있는 본부는 1번 마을 왼쪽에 있다. 이 트럭은 본부에서 출발하여 1번 마을부터 마지막 마을까지 오른쪽으로 가면서 마을에 있는 물건을 배송한다. 
2. 각 마을은 배송할 물건들을 박스에 넣어 보내며, 본부에서는 박스를 보내는 마을번호, 박스를 받는 마을번호와 보낼 박스의 개수를 알고 있다. 박스들은 모두 크기가 같다. 트럭에 최대로 실을 수 있는 박스의 개수, 즉 트럭의 용량이 있다. 이 트럭 한대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 한다.
	a. 조건 1: 박스를 트럭에 실으면, 이 박스는 받는 마을에서만 내린다.
	b. 조건 2: 트럭은 지나온 마을로 되돌아가지 않는다.
	c. 조건 3: 박스들 중 일부만 배송할 수도 있다.
3. 마을의 개수, 트럭의 용량, 박스 정보(보내는 마을번호, 받는 마을번호, 박스 개수)가 주어질 때, 트럭 한 대로 배송할 수 있는 최대 박스 수를 구하는 프로그램을 작성하시오. 
4. 입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이상 10,000이하 정수이다. 다음 M개의 각 줄에 박스를 보내는 마을번호, 박스를 받는 마을번호, 보내는 박스 개수(1이상 10,000이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 박스를 받는 마을번호는 보내는 마을번호보다 크다. 

먼저 직관적으로 생각해볼 수 있는 것은 다음과 같습니다.

1. N은 최대 2000이고, M은 최대 10,000이기 대문에 O(N*M)의 시간복잡도로 문제를 해결할 수 있다.
2. 문제의 목표는 어떤 화물을 최적으로 실을 것인가? 이다.

2번의 경우 다음과 같은 생각을 할 수 있습니다.
최대한 많은 화물을 내려야한다.
미래의 선택지를 알고있기 때문에, 미래의 선택지까지 고려해서 선택한다.

미래의 선택지까지 고려하기 위해서 출발지에서 화물을 실을지 말지 결정하는 것이 아니라, 도착지에서 화물을 실을지 말지를 결정합니다.

list.sort((n1,n2)-> n1.end - n2.end);


 for (Node cur: list) {

     int min = cur.value;

     for (int i = cur.start; i < cur.end; i++) {
         min = Math.min(remain[i], min);
     }

     total += min;

     for (int i = cur.start; i < cur.end; i++) {
         remain[i] -= min;
     }
 }

 System.out.println(total);

결론적으로 위와 같은 핵심 코드가 나올 수 있습니다.
출발지(start), 도착지(end), 화물 무게(value)의 정보를 담고 있는 Node클래스의 리스트인 list를 도착지를 기준으로 오름차순정렬합니다.
화물 출발지(start)부터 도착지 직전(end-1)까지의 최소값만큼 실을 수 있습니다.

시간 복잡도
O(N * M)

코드

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


public class Main {
	
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        List<Node> list = new ArrayList<>();
        

        int n = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(st.nextToken());

        
        
        st = new StringTokenizer(br.readLine());
        
        int m = Integer.parseInt(st.nextToken());
        
        int[] remain = new int[n+1];
        
        Arrays.fill(remain, c);
        
        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());
        	
        	list.add(new Node(start, end, value));
        }
        
        
        list.sort((n1,n2)-> n1.end - n2.end);
        
        int total = 0;
       
        
        for (Node cur : list) {
        	
        	int min = cur.value;
        	
        	for (int i=cur.start; i<cur.end; i++) {
        		min = Math.min(remain[i], min);
        	}
        	
        	total += min;
        	
        	for (int i=cur.start; i<cur.end; i++) {
        		remain[i] -= min;
        	}
        }
        
        System.out.println(total);

    }
    

}