[Gold I] 택배 - 8980
성능 요약
메모리: 28232 KB, 시간: 384 ms
분류
그리디 알고리즘, 정렬
문제 설명
아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽으로 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이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 박스를 받는 마을번호는 보내는 마을번호보다 크다.
출력
트럭 한 대로 배송할 수 있는 최대 박스 수를 한 줄에 출력한다.
풀이
O(N^2) 시간 복잡도로 해결할 수 있는 문제였다. truck 배열에 마을을 지나갈 때 트럭에 담겨있는 박스의 개수를 저장하였고, 배송요청을 배송지를 기준으로 정렬하였다. 출발지에서 최대 담을 수 있는 박스의 개수를 초과하였다면, 넘어가고, 그게 아니면 출발지부터 배송지까지 박스의 최대 개수를 구하고, 담을 수 있는 최대 박스의 개수에서 구한 값을 뺀 값을 truck 출발지부터 배송지까지 더해주면서 답을 구할 수 있었다.
import java.io.*;
import java.util.*;
class Main {
public static final BufferedReader BR = new BufferedReader(new InputStreamReader(System.in));
public static final BufferedWriter BW = new BufferedWriter(new OutputStreamWriter(System.out));
int N;
int C;
int M;
int[][] delivery;
int[] truck;
int[] delivered;
public static void main(String[] args) throws Exception {
Main main = new Main();
main.init();
main.solution();
}
void init() throws Exception {
int[] inputArray = Arrays.stream(BR.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
N = inputArray[0];
C = inputArray[1];
M = Integer.parseInt(BR.readLine());
delivery = new int[M][3];
truck = new int[N];
delivered = new int[N];
Arrays.fill(truck, 0);
Arrays.fill(delivered, 0);
for (int i = 0; i < M; i++) {
int[] villageAndBoxes = Arrays.stream(BR.readLine().split(" ")).mapToInt(Integer::parseInt).toArray();
delivery[i][0] = villageAndBoxes[0] - 1;
delivery[i][1] = villageAndBoxes[1] - 1;
delivery[i][2] = villageAndBoxes[2];
}
}
void solution() throws Exception {
long answer = 0;
Arrays.sort(delivery, Comparator.comparing((int[] orders) -> orders[1]));
for (int[] deliver : delivery) {
int start = deliver[0];
int destination = deliver[1];
int amount = deliver[2];
int currentWeight = truck[start];
if (currentWeight != C) {
int currentMaximum = currentWeight;
for (int i = start + 1; i < destination; i++) {
if (truck[i] > currentMaximum) {
currentMaximum = truck[i];
}
if (currentMaximum == C) {
break;
}
}
if (currentMaximum != C) {
int toAdd = Math.min(C - currentMaximum, amount);
answer += toAdd;
for (int i = start; i < destination; i++) {
truck[i] += toAdd;
}
}
}
}
System.out.println(answer);
}
}