[백준OJ] 8980번 택배 (Java)

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

8980번: 택배

---

 

풀이

그리디하게 문제를 해결하기 위해서 먼저 도착지점을 기준으로 오름차순 정렬을, 도착지점이 같다면 출발지점을 기준으로 오름차순 정렬을 했습니다.

 

예제 1번을 가져와 보면 아래와 같이 정렬됩니다.

보내는 마을	받는 마을	박스 개수
1	2	10
1	3	20
2	3	10
1	4	30
2	4	20
3	4	20

 

그런 뒤, 각 마을에서의 관점에서 현재 트럭에 존재하는 박스의 개수를 담는 배열을 만듭니다.

1번 마을	2번 마을	3번 마을	4번 마을
0개	0개	0개	0개

 

첫번째 택배를 추가한다면 1번마을에서는 10개의 박스가 추가될것입니다. 2번마을에 도착하면 어차피 내리기 때문에 도착마을 전까지만 추가해줍니다.

1번 마을	2번 마을	3번 마을	4번 마을
10개	0개	0개	0개

 

두번째 택배를 추가한다면 1번~2번마을에 20개가 추가될 것 입니다.

1번 마을	2번 마을	3번 마을	4번 마을
30개	20개	0개	0개

 

세번째 택배를 추가한다면, 2번 마을에 10개가 추가될 것 입니다.

1번 마을	2번 마을	3번 마을	4번 마을
30개	30개	0개	0개

 

네번째 택배를 추가한다면, 1번~3번 마을에 30개가 추가될 것 입니다. 하지만 트럭의 최대 용량이 40이기 때문에 이를 고려해주어야 합니다.

1번마을에선 40개중 10개, 2번마을에선 40개중 10개, 3번마을에선 40개중 40개 전부 가능합니다. 이중, 1번~3번까지 가져가야 하기때문에 최소값인 10개를 추가시켜줍니다.

1번 마을	2번 마을	3번 마을	4번 마을
40개	40개	10개	0개

 

다섯번째 택배를 추가한다면, 2번,3번 마을에 추가를 해주어야 합니다.

2번 마을에서는 20개의 박스중, 0개의 박스를 실을 수 있습니다.

3번 마을에서는 20개의 박스중 20개 모두 실을 수 있습니다. 

따라서 이 택배는 20개중 0개를 실을 수 있습니다. 이를 추가시켜줍니다.

1번 마을	2번 마을	3번 마을	4번 마을
40개	40개	10개	0개

 

여섯번째 택배를 추가한다면 3번째 마을에 추가시켜줘야합니다.

3번째 마을에선 20개 모두 실어도 최대용량을 넘지 않으므로 20개 모두 추가시켜줍니다.

1번 마을	2번 마을	3번 마을	4번 마을
40개	40개	30개	0개

 

따라서 1번째 택배(10개) + 2번째 택배(20개) + 3번째 택배(10개) + 4번째 택배(10개) + 5번째 택배(0개) + 6번째 택배(20개) = 70개가 됩니다.

 

시간복잡도

정렬 : O(MlogM)

그리디 : O(MN)

 

풀이

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    static class Node implements Comparable<Node>{
        int from,to,box;
        public Node(int from,int to,int box ){
            this.from = from;
            this.to=to;
            this.box = box;
        }

        @Override
        public int compareTo(Node o) {
            if(this.to == o.to){
                return this.from - o.from;
            }
            return this.to-o.to;
        }
    }
    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.valueOf(st.nextToken());
        int c = Integer.valueOf(st.nextToken());

        int m = Integer.valueOf(br.readLine());
        ArrayList<Node> nodes = new ArrayList<>();

        for(int i=0;i<m;i++){
            st = new StringTokenizer(br.readLine());

            int from = Integer.valueOf(st.nextToken());
            int to = Integer.valueOf(st.nextToken());
            int box = Integer.valueOf(st.nextToken());

            nodes.add(new Node(from,to,box));
        }

        Collections.sort(nodes);

        int[] boxes = new int[n+1];
        int answer = 0;

        for(Node node : nodes){
            int from = node.from;
            int to = node.to;
            int box = node.box;

            int valid = Integer.MAX_VALUE;//최대로 많이 실을 수 있는 박스 개수
            for(int i=from;i <to;i ++){
                int extra = Math.min(c-boxes[i],box);
                valid = Math.min(valid,extra);
            }
            answer+=valid;
            for(int i=from;i<to;i++){
                boxes[i]+=valid;
            }
        }
        System.out.println(answer);
    }
}