BOJ 8980 택배
https://www.acmicpc.net/problem/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 | 15 | 보내는 마을번호는 모두 1, N ≤ 20 |
| 2 | 17 | 받는 마을번호는 N-1 또는 N, 3 ≤ N ≤ 20 |
| 3 | 20 | N ≤ 5, M ≤ 5, C ≤ 10 |
| 4 | 23 | N ≤ 100, M ≤ 1,000, C ≤ 2,000 |
| 5 | 25 | 추가적인 제약조건은 없다. |
예제 입력 1
4 40 6 3 4 20 1 2 10 1 3 20 1 4 30 2 3 10 2 4 20
예제 출력 1
70
예제 입력 2
6 60 5 1 2 30 2 5 70 5 6 60 3 4 40 1 6 40
예제 출력 2
150
코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;
/**
* 택배의 도착 마을 번호를 오름차순으로, 도착 마을 번호가 같다면 출발 마을 번호를 오름차순으로
* 박스 정보를 뽑아 배송할 수 있는 최대 박스 수를 계산한다.
* 박스를 운송하는 동안 트럭에서 공간을 차지하고 있기 때문에,
* 각 마을로 배송하는 동안 트럭의 용량을 체크하고 있어야 한다.
*/
public class Main {
static class Box implements Comparable<Box> {
int start, end, count;
public Box(int start, int end, int count) {
this.start = start;
this.end = end;
this.count = count;
}
@Override
public int compareTo(Box o) {
if(end == o.end) return start - o.start;
return end - o.end;
}
}
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()),
C = Integer.parseInt(st.nextToken()),
M = Integer.parseInt(br.readLine());
PriorityQueue<Box> queue = new PriorityQueue<>();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
queue.offer(new Box(
Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken()),
Integer.parseInt(st.nextToken())
));
}
// 각 마을에서 실을 수 있는 박스의 개수를 의미하는 배열
int[] loadable = new int[N + 1];
Arrays.fill(loadable, C);
int answer = 0;
while (!queue.isEmpty()) {
Box check = queue.poll();
// 확인 중인 박스 정보에서 트럭에 실을 수 있는 최대 박스 수를 계산하기 위한 변수
int max = check.count;
/**
* 배송을 시작할 마을부터 배송을 완료하기 전 마을까지 중에서
* 가장 적게 배송할 수 있는 마을을 기준으로 최대 박스 수를 설정
*/
for (int i = check.start; i < check.end; i++)
if(max > loadable[i]) max = loadable[i];
// 배송할 박스 수를 정답에 추가하고 배송 시작일부터 완료일 전까지 배송 가능한 박스 수에서 해당 박스 수를 차감
answer += max;
for (int i = check.start; i < check.end; i++)
loadable[i] -= max;
}
System.out.println(answer);
}
}