[백준 2212] 택배

택배

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	3883	1323	969	36.292%

문제

아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽으로 1번부터 차례대로 번호가 붙여진 마을들이 있다. 마을에 있는 물건을 배송하기 위한 트럭 한 대가 있고, 트럭이 있는 본부는 1번 마을 왼쪽에 있다. 이 트럭은 본부에서 출발하여 1번 마을부터 마지막 마을까지 오른쪽으로 가면서 마을에 있는 물건을 배송한다.

각 마을은 배송할 물건들을 박스에 넣어 보내며, 본부에서는 박스를 보내는 마을번호, 박스를 받는 마을번호와 보낼 박스의 개수를 알고 있다. 박스들은 모두 크기가 같다. 트럭에 최대로 실을 수 있는 박스의 개수, 즉 트럭의 용량이 있다. 이 트럭 한대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 한다.

• 조건 1: 박스를 트럭에 실으면, 이 박스는 받는 마을에서만 내린다.
• 조건 2: 트럭은 지나온 마을로 되돌아가지 않는다.
• 조건 3: 박스들 중 일부만 배송할 수도 있다.

마을의 개수, 트럭의 용량, 박스 정보(보내는 마을 번호, 받는 마을번호, 박스 개수)가 주어질 때, 트럭 한 대로 배송할 수 있는 최대 박스 수를 구하는 프로그램을 작성하시오. 단, 받는 마을번호는 보내는 마을번호보다 항상 크다.

예를 들어, 트럭 용량이 40이고 보내는 박스들이 다음 표와 같다고 하자.

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

이들 박스에 대하여 다음과 같이 배송하는 방법을 고려해 보자.

(1) 1번 마을에 도착하면

다음과 같이 박스들을 트럭에 싣는다. (1번 마을에서 4번 마을로 보내는 박스는 30개 중 10개를 싣는다.)

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

(2) 2번 마을에 도착하면

트럭에 실려진 박스들 중 받는 마을번호가 2인 박스 10개를 내려 배송한다. (이때 트럭에 남아있는 박스는 30개가 된다.)

그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 40개가 된다.)

보내는 마을	받는 마을	박스 개수
2	3	10

(3) 3번 마을에 도착하면

트럭에 실려진 박스들 중 받는 마을번호가 3인 박스 30개를 내려 배송한다. (이때 트럭에 남아있는 박스는 10개가 된다.)

그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 30개가 된다.)

보내는 마을	받는 마을	박스 개수
3	4	20

(4) 4번 마을에 도착하면

받는 마을번호가 4인 박스 30개를 내려 배송한다

위와 같이 배송하면 배송한 전체 박스는 70개이다. 이는 배송할 수 있는 최대 박스 개수이다.

입력

입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이상 10,000이하 정수이다. 다음 M개의 각 줄에 박스를 보내는 마을번호, 박스를 받는 마을번호, 보내는 박스 개수(1이상 10,000이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 박스를 받는 마을번호는 보내는 마을번호보다 크다.

출력

트럭 한 대로 배송할 수 있는 최대 박스 수를 한 줄에 출력한다.

예제 입력 1

xxxxxxxxxx
4 40
6
3 4 20
1 2 10
1 3 20
1 4 30
2 3 10
2 4 20

예제 출력 1

xxxxxxxxxx
70

 

풀이

그리디 문제 유형은 답을 생각하기가 참 어려운것 같습니다.

 

택배는 1번 마을 ~ N번 마을순으로 움직이며 한 번 지나간 곳은 다시 돌아올수 없습니다.

그래서 맨 처음에 생각 한 것은 단순히 보내는 마을을 순서로 정렬을 하면 어떨까 라고 생각했습니다.

 

근데 그럴경우, 만약 도시가 1000개있고 택배가 40개 까지 보낼수 있다면

1번 ->1000번 = 40개

2번 -> 3번 = 40개

3번->4번 = 40개

 

이런 예시일 경우 답이 맞지 않습니다.

 

그래서 택배를 받는 도시를 기준으로 정렬을 했습니다. 받는도시가 같다면 출발도시가 작은순으로 정렬합니다

위의 예시에서 받는 도시로 정렬을 하면

2번->3번 40개

3번->4번 40개

1번->1000번 40개

 

이렇게 되는데, 이 경우 80개를 구할수 있게 됩니다.

 

또 어려웠던건 트럭의 용량인데, 이를 각 마을별로 보낼수있는 양으로 처리를 합니다.

 

예를들어 트럭의 최대용량이 40이라고 마을이 4개있다면

 

처음에는 각 마을이 보낼수 있는 양은

 

마을1번 : 40

마을 2번:40

마을 3번:40

마을 4번:40

 

이렇게 됩니다.

 

예를들어서 마을 1 -> 마을 2로 택배 20개를 보낸다고 가정을 해 볼까요?

그러면

마을 1에서 택배 20개 보냈으니

각 마을이 보낼수 있는 양은

마을 1번: 20개

마을 2번:40개

마을 3번: 40개

마을 4번 : 40개

 

이렇게 됩니다. 왜 트럭이 수용할수있는 최대량을 각 마을별로 나눠주었냐에 이해가 한번에 되지 않았습니다.

 

이는 한 번 지나온 마을은 되돌아가지 않기 때문입니다.

다른 예를 들어볼까요

 

마을 1-> 마을2로 택배 20개를 보낸 상태에서

마을 1-> 마을3으로 택배 20개를 보낸다고 하면

 

지금 위의 표에서는 마을 1번은 20개를 더 보낼수 있습니다

이걸 트럭의 최대수용량과 비교해보면 똑같은 것을 알 수 있습니다.

 

마을 1-> 마을 3번으로 택배를 보내면

마을 1 : 0

마을 2: 20

마을 3: 40

마을 4: 40

 

이렇게 됩니다.

 

2번 마을 또한 현재 1번->3번 마을로 택배를 보냈으니 택배의 수거량에 포함되어 있으니 마을 2번도 제거해주면 됩니다.

 

 

또 다른 케이스를 생각해볼까요

마을 2번은 20개를 보낼수있고

마을 3번은 20개를 보낼수 있다고 가정합시다.

 

마을 1에서 마을4까지 보내는데, 만약 그 무게가 30이라면 어떻게 해야 할까요?

30을 다 보내면 트럭의 용량이 초과합니다.

 

이 경우 따로 계산을 해서 20개만 보내면 됩니다.

 

 

전체코드

 

import java.io.*;
import java.util.*;
import java.math.*;
public class Main {
    static int n,c;
    static int dp[][];
    static int arr[];
    static int ans =0;
    static ArrayList<Node>list = new ArrayList<>();
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        String [] t = br.readLine().split(" ");
        n = Integer.parseInt(t[0]);
        c = Integer.parseInt(t[1]);     // 트럭이 적재가능한 양
        arr = new int[n];
        int m = Integer.parseInt(br.readLine());    // 박수의 개수
        
        
        for(int i=1; i<n; i++) {
            arr[i] = c;
        }
        
        for(int i=0; i<m; i++) {
            String [] tt =br.readLine().split(" ");
            int s = Integer.parseInt(tt[0]);
            int e = Integer.parseInt(tt[1]);
            int w = Integer.parseInt(tt[2]);
            list.add(new Node(s,e,w));
        }
        Collections.sort(list);
        
        for(int i=0; i<list.size(); i++) {
            Node a = list.get(i);
            int min = Integer.MAX_VALUE;
            
            for(int j= a.start; j<a.end; j++) {
                min = Math.min(min, arr[j]);
            }
            
            if(min-a.w<0) {
                for(int j=a.start; j<a.end; j++) {
                    arr[j]-=min;
                }
                ans+=min;
            }
            else {
                ans+=a.w;
                for(int j=a.start; j<a.end; j++) {
                    arr[j]-=a.w;
                }
            }
            
        }
        System.out.println(ans);
    }
}
class Node implements Comparable<Node>{
    int start, end,  w;
    Node(int start, int end ,int w){
        this.start=start;
        this.end = end;
        this.w=w;
    }
    @Override
    public int compareTo(Node o) {
        if(this.end == o.end) {
            return this.start-o.start;
        }
        else {
            return this.end-o.end;
        }
    }
    
}