[BOJ] 8980.택배
백준 알고리즘 문제 풀이
해당 문제는 그리디 방식으로 풀어보았습니다.
링크 : 
1. 문제
문제 보기
| 시간 제한 | 메모리 제한 |
|---|---|
| 1 초 | 128 MB |
직선 도로상에 왼쪽부터 오른쪽으로 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 | 30 |
(2) 2번 마을에 도착하면
- 트럭에 실려진 박스들 중 받는 마을번호가 2인 박스 10개를 내려 배송한다. (이때 트럭에 남아있는 박스는 30개가 된다.)
- 그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 40개가 된다.)
| 보내는 마을 | 받는 마을 | 박스 개수 |
|---|---|---|
| 2 | 3 | 10 |
(3) 3번 마을에 도착하면
- 트럭에 실려진 박스들 중 받는 마을번호가 3인 박스 30개를 내려 배송한다. (이때 트럭에 남아있는 박스는 10개가 된다.)
- 그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 30개가 된다.)
| 보내는 마을 | 받는 마을 | 박스 개수 |
|---|---|---|
| 3 | 4 | 20 |
(4) 4번 마을에 도착하면
- 받는 마을번호가 4인 박스 30개를 내려 배송한다.
위와 같이 배송하면 배송한 전체 박스는 70개이다. 이는 배송할 수 있는 최대 박스 개수이다.
입력(Input)
입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이상 10,000이하 정수이다. 다음 M개의 각 줄에 박스를 보내는 마을번호, 박스를 받는 마을번호, 보내는 박스 개수(1이상 10,000이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 박스를 받는 마을번호는 보내는 마을번호보다 크다.
출력(Output)
트럭 한 대로 배송할 수 있는 최대 박스 수를 한 줄에 출력한다.
서브태스크
| 번호 | 배점 | 제한 |
|---|---|---|
| 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 | 추가적인 제약조건은 없다. |
2. 문제 풀이
처음에 그냥 그리디적 가벼운 접근으로 해결하려고 하니 답이 나오지 않았다.
주어진 조건에서 택배의 거리로 짧은 순서대로 정렬하고 현 위치에서 싣을 수 있는 가장 많은 택배만큼 싣고 가려고 했었다.
그러나 그렇게 접근하니 예외처리를 해야하는 부분에서 오류가 발생하였다.
몇 시간을 헤매이다가 결국에는 힌트를 보고서 문제를 해결 할 수 있었다.
- 마을 별로 내리는 짐의 개수 대신에 K 마을에 방문해서 짐을 내린 후, 트럭에 싣고 있는 박스의 개수를 파악한다.
- 보내는 마을과 받는 마을의 거리가 멀수록 보내는 마을로부터 다음 마을들을 순차적으로 방문할 때마다 받는 마을 바로 직전의 마을까지 짐을 계속해서 들고 있어야 한다.
- 그 사이에 더 큰 짐을 싣고 내리는 경우가 있을 수 있기 때문에 보내는 마을과 받는 마을의 거리가 멀면 그만큼 손해를 볼 수 있다.
- ‘무조건 1번 마을부터 N번 마을까지 순차적으로 방문한다는 조건’ & ‘보내는 마을보다 무조건 받는 마을의 번호가 높다는 조건’ 이 두 조건을 활용하는 것으로 문제를 풀 수 있다.
그렇다면 보내는 마을이 받는 마을과 거리가 가깝다는 뜻은 받는 마을의 번호를 오름차순으로 정렬했을 때 가장 앞에 있을수록 가깝다는 뜻이 된다.
그 다음 우선순위로는 보내는 마을을 오름차순으로 정렬하는 것이다.
** 두 번째 우선순위는 굳이 안해도 풀 수 있다.
즉! 아래의 단계로 해결 할 수 있었다.
- 받는 마을 번호를 오름차순으로 정렬
- 각 마을 별로 박스의 개수를 파악할 수 있는 Array 생성
- 앞에서부터 (보내는 마을, 받는 마을, 박스 개수) 를 꺼내서 사용
** 참고로, 받는 마을에서 박스 개수는 고려하지 않는다. 도착하면 박스를 내리기 때문에
2의 추가 내용
- 정렬 후
| 보내는 마을 | 받는 마을 | 박스 개수 |
|---|---|---|
| 1 | 2 | 10 |
| 2 | 3 | 10 |
| 1 | 3 | 20 |
| 3 | 4 | 20 |
| 2 | 4 | 20 |
| 1 | 4 | 30 |
3) 추가 내용
- 1번 째 꺼낸 경우
트럭의 용량 : 40
마을 : 1 // 2 // 3 // 4
마을에서의 트럭에 싣은 박스 개수 : 10 // 0 // 0 // 0 ( +10 내림 = 10)
- 2번 째 꺼낸 경우
트럭의 용량 : 40
마을 : 1 // 2 // 3 // 4
마을에서의 트럭에 싣은 박스 개수 : 10 // 10 // 0 // 0 ( + 10 내림 = 20)
- 3번 째 꺼낸 경우
트럭의 용량 : 40
마을 : 1 // 2 // 3 // 4
마을에서의 트럭에 싣은 박스 개수 : 30(+20) // 30(+20) // 0 // 0 ( + 20 내림 = 40)
- 4번 째 꺼낸 경우
트럭의 용량 : 40
마을 : 1 // 2 // 3 // 4
마을에서의 트럭에 싣은 박스 개수 : 30 // 30 // 20(+ 20) // 0 ( + 20 내림 = 60)
- 5번 째 꺼낸 경우
트럭의 용량 : 40
마을 : 1 // 2 // 3 // 4
마을에서의 트럭에 싣은 박스 개수 : 30 // 40(+10) // 30(+ 10) // 0 ( + 10 내림 = 70)
** 트럭의 용량이 40이기 때문에 2번 마을에 박스가 20개나 있음에도 불구하고 10만 싣을 수 있다.
** 3번 마을에는 2번에서 10만 싣었으니 당연히 10이 추가된다.
- 6번 째 꺼낸 경우
트럭의 용량 : 40
마을 : 1 // 2 // 3 // 4
마을에서의 트럭에 싣은 박스 개수 : 30 // 40 // 30 // 0 ( + 0 내림 = 70)
따라서 최대 옮기는 박스의 개수는 70개가 된다.
3. 소스 코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.StringTokenizer;
public class ParcelService_8980 {
public int solution(int n, int c, ArrayList<TownBoxes> townboxes) {
Collections.sort(townboxes);
int[] boxes = new int[n + 1];
int boxCount = 0;
for(TownBoxes town : townboxes) {
int start = town.start;
int end = town.end;
int box = town.boxes;
int max = 0;
boolean isLoad = true;
for(int i = start; i < end; i++) {
if(boxes[i] >= c) {
isLoad = false;
break;
}
max = Math.max(boxes[i], max);
}
if(isLoad) {
int dropOff = c - max;
if(dropOff > box) {
dropOff = box;
}
boxCount += dropOff;
for(int i = start; i < end; i++) {
boxes[i] += dropOff;
}
}
}
return boxCount;
}
public static void main(String[] args) throws IOException {
ParcelService_8980 mc = new ParcelService_8980();
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());
st = new StringTokenizer(br.readLine());
int M = Integer.parseInt(st.nextToken());
ArrayList<TownBoxes> boxes = new ArrayList<>();
for (int i = 0; i < M; i++) {
st = new StringTokenizer(br.readLine());
int start = Integer.parseInt(st.nextToken());
int end = Integer.parseInt(st.nextToken());
int box = Integer.parseInt(st.nextToken());
boxes.add(new TownBoxes(start, end, box));
}
System.out.println(mc.solution(N, C, boxes));
}
}
class TownBoxes implements Comparable<TownBoxes> {
int start = 0;
int end = 0;
int boxes = 0;
TownBoxes(int start, int end, int boxes) {
this.start = start;
this.end = end;
this.boxes = boxes;
}
@Override
public int compareTo(TownBoxes box) {
if(this.end == box.end) return this.start - box.start;
else return this.end - box.end;
}
}
