[백준]JAVA - 8980번: 택배

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

8980번: 택배

·

·

·

(이하 생략)

 

🔶 풀이

필자는 해당 문제를 아래와 같은 순서대로 풀었다.

 

1. 박스 정보를 가까운 순으로 정렬하기.

: 거리가 먼 박스를 싣고 이동하면 중간에 옮길 수 있는 상자를 놓칠 수 있다.

따라서, 받는 마을이 가까운 순으로 정렬해 주고, 보내는 마을을 가까운 순으로 정렬해 주면 된다.

public static class Box implements Comparable<Box> {
    int s, e, cnt;
        
    public Box(int s, int e, int w) {
        this.s = s;
        this.e = e;
        this.cnt = cnt;
    }
        
    public int compareTo(Box o) {
        if (this.e == o.e) { 
            return this.s - o.s;
        }
            
        return this.e - o.e;
    }
}

번호가 낮을수록 출발 지점에서 가까운 마을이라고 했으므로 둘 다 오름차순으로 정렬해주면 된다.

 

2. 각 마을 정보를 담는 배열(town)을 트럭이 최대로 옮길 수 있는 개수(C)로 초기화해 줬다.

3. 박스 정보를 하나씩 꺼내서 보내는 마을에서 받는 마을 전까지의 실을 수 있는 최소 개수를 구한다.

: 받는 마을에 도착하자마자 개수가 빠지기 때문에 받는 마을 전(N-1)까지만 구하면 된다.

 

4. 현재 박스의 개수와 최소 개수를 비교 후에 마을 정보를 담는 배열(town)에서 빼주고, 배달이 완료된 개수(ans)에 더해준다.

5. 3~4번 과정을 반복한다.

 

예시

<트럭이 최대로 담을 수 있는 용량: 40>

보내는 마을 (s)	받는 마을 (e)	박스 개수 (cnt)
1	2	10
1	3	20
2	3	10
1	4	30
2	4	20
3	4	20

예제 1번을 받는 마을이 가까운 순으로, 같다면 보내는 마을이 가까운 순으로 정렬을 완료했다.

 

<town 배열>

마을	1	2	3
최대 개수	40	40	40

2번 과정, 각 마을 정보를 담는 배열에 트럭이 최대로 옮길 수 있는 개수로 초기화해 준다. 마지막 마을에서는 박스를 실지 않기 때문에 4번 마을까지 생각할 필요가 없다.

 

첫 번째 박스 정보는 보내는 마을: 1 / 받는 마을: 2 / 박스 개수: 10

1번부터 1(2-1)번 마을까지의 현재 담을 수 있는 개수 중 최소 개수는 40 이므로 박스를 싣고 옮기는 게 가능하다.

해당 경로에 포함된 각 마을의 최대 개수에서 10을 빼준 후에 ans 변수에 10을 더한다. 

마을	1	2	3
최대 개수	30	40	40

ans = 10;

 

두 번째 박스 정보는 보내는 마을: 1 / 받는 마을: 3/ 박스 개수: 20

1번부터 2(3-1)번 마을까지의 현재 담을 수 있는 개수 중 최소 개수는 30이므로 박스를 싣고 옮기는게 가능하다.

해당 경로에 포함된 각 마을의 최대 개수에서 20을 빼준 후에 ans 변수에 20을 더한다.

마을	1	2	3
최대 개수	10	20	40

ans = 30;

 

세 번째 박스 정보는 보내는 마을: 2 / 받는 마을: 3 / 박스 개수: 10

2번부터 2(3-1)번 마을까지의 현재 담을 수 있는 개수 중 최소 개수는 20이므로 박스를 싣고 옮기는 게 가능하다.

해당 경로에 포함된 각 마을의 최대 개수에서 10을 빼준 후에 ans 변수에 10을 더한다.

마을	1	2	3
최대 개수	10	10	40

ans = 40;

 

네 번째 박스 정보는 보내는 마을: 1 / 받는 마을: 4 / 박스 개수: 30

1번부터 3번 마을까지의 현재 담을 수 있는 개수 중 최소 개수는 10이므로 모든 박스를 옮길 수 없다.

따라서 해당 경로에 포함된 각 마을의 최대 개수에서 10을 빼준 후에 ans 변수에 10을 더한다.

마을	1	2	3
최대 개수	0	0	30

ans = 50;

 

다섯 번째 박스 정보는 보내는 마을: 2 / 받는 마을: 4 / 박스 개수: 20

2번부터 3번 마을까지의 현재 담을 수 있는 개수 중 최소 개수는 0이므로 박스를 싣고 옮기는 게 불가능하다.

ans = 50;

 

마지막 박스 정보는 보내는 마을: 3 / 받는 마을: 4 / 박스 개수: 20

3번부터 3(4-1)번 마을까지의 현재 담을 수 있는 개수 중 최소 개수는 30이므로 박스를 싣고 옮기는 게 가능하다.

마을	1	2	3
최대 개수	0	0	10

ans = 70;

 

 

<최종코드>

import java.io.*;
import java.util.*;

public class Main { 
    public static class Box implements Comparable<Box> {
        int s, e, cnt;
        
        public Box(int s, int e, int w) {
            this.s = s;
            this.e = e;
            this.cnt = cnt;
        }
        
        public int compareTo(Box o) {
            if (this.e == o.e) { 
                return this.s - o.s;
            }
            
            return this.e - o.e;
        }
    }
    
    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.parseInt(st.nextToken()); // 마을 수
        int C = Integer.parseInt(st.nextToken()); // 트럭의 용량
        int M = Integer.parseInt(br.readLine());  // 보내는 박스 정보 개수
        
        ArrayList<Box> box = new ArrayList<>();
        
        for (int i=0; i<M; i++) {
            st = new StringTokenizer(br.readLine());
            
            int s = Integer.parseInt(st.nextToken());
            int e = Integer.parseInt(st.nextToken());
            int cnt = Integer.parseInt(st.nextToken());
            
            box.add(new Box(s, e, cnt));
        }
        
        Collections.sort(box);
        int[] town = new int[N];
        Arrays.fill(town, C);
        
        int ans = 0;
        for (int i=0; i<M; i++) {
            Box b = box.get(i);
            
            // 출발지에서 도착지까지의 옮길 수 있는 최대 무게
            int min = Integer.MAX_VALUE;
            for (int j=b.s; j<b.e; j++) {
                min = Math.min(min, town[j]);
            }
            
            // 최대로 다 옮길 수 있을 경우 (모든 짐을 옮김)
            if (min >= b.cnt) {
                for (int j=b.s; j<b.e; j++) {
                    town[j] -= b.cnt;
                }
                ans += b.cnt;
            
            // 남은 공간만 채우기
            } else {
                for (int j=b.s; j<b.e; j++) {
                    town[j] -= min;
                }
                ans += min;
            }
        }
        
        System.out.println(ans);
    }
}