[PS] BOJ8980 택배 ( greedy ) with JAVA

8980번: 택배

 

 

◎ 문제풀이

 

각 지점에서 트럭이 택배를 싣고 내릴 때, 최대 몇 개의 택배를 전달할 수 있는지 묻는 문제이다.

 

가장 최적의 상황을 발상하기 어려운 문제였다. 

 

처음에는 시작점을 오름차순하고 그 다음 도착점을 오름차순하여 택배를 트럭에 싣는 방식을 생각했다. 그러나 문제가 있었다. 지점이 1 부터 5까지 있다고 해보자. 1을 시작으로 하고 5를 도착으로 하는 택배는 1부터 5까지 트럭이 이동하는 동안 공간을 차지하고 있게 된다. 이는 최적의 상황이라고 할 수 없다. 

 

그러므로 정반대로 해야한다.

 

도착점을 오름차순하고 그다음 시작점으로 오름차순해서 택배를 트럭에 실어야 한다. 도착점이 빠를수록 트럭의 공간이 생길 확률이 커진다. 만약 도착점이 같다면 시작점이 빠른 순으로 해야 하나라도 더 빠르게 택배를 배달 할 수 있다. 

 

 

 

 

 

 

1부터 5까지 지점이 있다.

각 지점에는 트럭에 택배를 실을 수 있는 최대용량을 존재한다. 처음에는 모든 지점이 40이다.

 

그럼 우선순위 1순위부터 보자.

 

출발점이 1이고 도착점이 3이다.  그럼 트럭이 1지점과 2지점을 30을 싣고 지나간다. 그럼 1지점과 2지점의 트럭에 실을 수 있는 택배개수는 -30이 된다. 

 

 

  

 

트럭이 이미 30을 싣고 있으니 1지점과 2지점을 지나갈 때는 10밖에 못 싣는다. 3지점에서는 택배를 내려놓으니 40을 실을 수 있다. 이렇게 트럭이 30을 옮겼다. 

 

그럼 우선순위2를 보자.

출발지는 1, 도착지는 4이고 택배수량은 10이니

1 지점, 2지점, 3지점을 10을 싣고 지나간다.

 

 

 

 

1지점과 2지점은 더 이상 실을 수 없다. 3지점은 30을 실을 수 있다. 이렇게 트럭은 10을 옮겼다. 

 

우선순위3은 출발점이 2이다. 그런데 2에서는 더이상 택배를 실을 수 없다.

우선순위4는 출발점이 1이다. 그런데 1에서는 더이상 택배를 실을 수 없다. 

 

그러므로 30 + 10 = 40 

 

40개가 답이 된다. 

 

그럼 이를 코드로 구현해보자. 

 

 

◎ 코드

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

//BOJ8980 택배
public class Main{

    public static class Deploy implements Comparable<Deploy>{

        int start;
        int des;
        int quantity;

        public Deploy(int start, int des,int quantity){
            this.start = start;
            this.des = des;
            this.quantity = quantity;
        }

        @Override
        public int compareTo(Deploy d) {
            if(this.des == d.des) return this.start - d.start;
            return this.des - d.des;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        int ans = 0;
        int n = Integer.parseInt(st.nextToken());
        int limit = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(br.readLine());

        PriorityQueue<Deploy>  pq = new PriorityQueue<>();
        int[] pos = new int[n+1];
        Arrays.fill(pos,limit);

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

            int start = Integer.parseInt(st.nextToken());
            int des = Integer.parseInt(st.nextToken());
            int quantity = Integer.parseInt(st.nextToken());

            pq.add(new Deploy(start,des,quantity));
        }

        while(!pq.isEmpty()){
            Deploy d = pq.remove();

            int start = d.start;
            int des = d.des;
            int quantity = d.quantity;

            int maxNum = Integer.MAX_VALUE;
            
            
            // 트럭에 실을 수 있는 최댓값 구하기 
            for(int i=start;i<des;i++){
                // 시작점과 도착점 사이 지점 중 실을 수 있는 최소 중량 구하기 
                maxNum = Math.min(maxNum,pos[i]);
            }
            
            // 택배 개수가 최댓값보다 작은 경우 
            if( maxNum >= quantity ){
                for(int i=start;i<des;i++){
                    pos[i] -= quantity;
                }
                ans += quantity;
            }
            
            // 택배 개수가 최댓값보다 큰 경우
            else {
                for(int i=start;i<des;i++){
                    pos[i] -= maxNum;
                }
                // 최대 개수의 택배만 이동
                ans += maxNum;
            }

        }

        System.out.println(ans);

    }

}