Baekjoon 8980 택배 JAVA

8980번: 택배

문제

아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽으로 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. 트럭은 좌측에서 우측으로만 이동 가능하다. 

들어오는 박스에 대한 정보를 class로 만들어 시작, 도착, 갯수를 저장한다.

2. 도착 도시를 기준으로 오름차순 정렬, 도착 도시가 같다면 시작 도시를 기준으로 오름차순 정렬

3. 시작도시부터 도착도시까지 가장 많이 적재된 박스 양을 찾음

4. 3에서 구한 값에 대해 추가 적재할 수 있는 양을 계산해서 값을 더함

5. j의 점에 4에서 구한 값을 더함

6. 3-5번을 M번 반복

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

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());
		int n= Integer.parseInt(st.nextToken()), c = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(br.readLine());
		Box [] boxes = new Box [m];
		for(int i=0;i<m;i++) {
			st = new StringTokenizer(br.readLine());
			int from = Integer.parseInt(st.nextToken());
			int to = Integer.parseInt(st.nextToken());
			int amount = Integer.parseInt(st.nextToken());
			boxes[i]=new Box(from, to, amount);
		}
		Arrays.sort(boxes);	// 입력받은 택배의 갯수를 1.도착점 기준으로 정렬, 2.도착점이 동일하다면 출발점 기준으로 정렬
		int [] deli = new int[n+1];	// 최대 배송가능한 택배의 개수
		int ans=0;
		
		for(int i=0;i<m;i++) {
			int max=0;	// 택배배송 할 수 있는 최대 갯수
			// 이미 존재하는 택배 배송 가능 갯수를 알면 max에 저장
			for(int j=boxes[i].from;j<boxes[i].to;j++)
				max=Math.max(max, deli[j]);
			// 이동 범위를 탐색하면서 그 범위에서 최대 운송가능한 C를 넘지 않으면 운송이 가능한 최대 갯수를 찾을 수 있다.
			for(int j=boxes[i].from;j<boxes[i].to;j++)
				// 만약 현재 들고있는게 30개, 최대 운송수량이 40개, i에서의 갯수가 100개라면 추가적으로 가질수 있는 값은 10이다.
				// 40-30을해서 10개를 챙기도록 한다
				deli[j]+=Math.min(boxes[i].amount, c-max);
			
			ans+=Math.min(boxes[i].amount, c-max);
		}
		System.out.println(ans);
	}
	
	static class Box implements Comparable<Box>{
		int from, to, amount;

		public Box(int from, int to, int amount) {
			this.from = from;
			this.to = to;
			this.amount = amount;
		}

		@Override
		public int compareTo(Box o) {
			// 도착점이 동일하다면 출발점 증가하는 순서로 작성
			if(this.to==o.to)
				return this.from-o.from;
			// 도착점이 빠른곳 부터 느린곳 순서대로 증가
			return this.to-o.to;
		}
	}
}