백준 8980 택배 문제 풀이
백준 온라인 저지, 8980번: 택배
도입
주어진 구간별로 배송이 필요한 택배 상자 양이 평이한 경향을 보인다면, 다소 많은 택배 상자의 배달을 요구하는 긴 구간보다 양이 적은 짧은 구간을 여러 개 선택하는 것이 더 낫다.
1번 마을에서 2번 마을 구간 $A$에서 10개의 택배 상자 배송을, 2번 마을에서 3번 마을 구간 $B$에서 5개의 택배 상자 배송을, 그리고 1번 마을에서 3번 마을 구간 $C$에서 $N$개의 택배 상자를 배송해야 한다고 가정한다.
이 상황에서 구간 $A$와 구간 $B$ 두 개를 선택하는 것과 구간 $C$ 한 개를 선택하는 것 차이에 총 배송량에는 차이가 없다. 하지만 대부분의 상황에서 두 구간을 선택하는 것이 잠재적으로 더 이롭다.
- 트럭의 용량이 10보다 작다면, 구간 $A$와 구간 $C$에서 요구하는 배송량을 모두 처리할 수는 없다. 하지만 구간 $C$의 배송을 처리하는 기회비용으로 구간 $A$의 배송량과 구간 $B$의 배송량 모두를 처리할 수 있다.
- 트럭의 용량이 10 이상 15 미만이라면, 구간 $A$와 구간 $B$가 요구하는 모든 배송량을 처리할 수 있다. 동시에 남는 용량을 구간 $C$, 혹은 다른 구간의 배송에 대응할 수 있다.
- 트럭의 용량이 15 이상이어도, 구간 $C$를 우선 선택하는 것보다 위의 2번과 같이 $A$와 $B$를 먼저 선택한 후 남는 용량을 구간 $C$의 대응에 사용하는 것이 더 낫다.
사실 위 상황은 “구간별로 배송량이 평이한” 것과 관계가 없다. 문제 상황에서는 트럭의 한계 용량이 결정되어있고 배송 구간마다의 택배를 모두 보내지 않고 일부만 보내는 것이 가능하므로, 항상 *더 짧은 구간을 우선 선택*하는 것이 좋다.
문제 풀이
예제 1의 택배 배송 상황을 (1) 구간의 길이 (2) 끝점 기준 (3) 박스 개수 순으로 오름차순 정렬하면 다음과 같다.1
1 사실 도입 문단에서 파악했듯, (1) 조건 외에는 큰 의미가 없다.
- 1 → 2 (길이 1, 끝점 2, 박스 10)
- 2 → 3 (길이 1, 끝점 3, 박스 10)
- 3 → 4 (길이 1, 끝점 4, 박스 20)
- 1 → 3 (길이 2, 끝점 3, 박스 20)
- 2 → 4 (길이 2, 끝점 4, 박스 20)
- 1 → 4 (길이 3, 끝점 4, 박스 30)
우선 1. ~ 3. 구간을 모두 선택하더라도 트럭의 용량 40을 초과하지 않으므로, 구간을 더 선택할 수 있다.
| 1 → 2 | 2 → 3 | 3 → 4 | 합계 |
|---|---|---|---|
| 10/40 1 | 10/40 2 | 20/40 3 | 40 |
1, 2, 3번 구간의 배송량을 처리하기로 했음에도, 4번 구간의 배송량을 온전히 처리할 수 있다.
| 1 → 2 | 2 → 3 | 3 → 4 | 합계 |
|---|---|---|---|
| 30/40 1, 4 | 30/40 2, 4 | 20/40 3 | 60 |
5번 구간의 배송량은 박스 20개이지만, 2 → 3 구간에서 트럭의 여유 수용 능력은 박스 10개뿐이다. 5번 구간에서는 박스 10개를 배송한다.
| 1 → 2 | 2 → 3 | 3 → 4 | 합계 |
|---|---|---|---|
| 30/40 1, 4 | 40/40 2, 4, 5 | 30/40 3, 5 | 70 |
6번 구간의 배송 수요에는 대응할 수 없다.
구현
1
2
3
4
5
6
7
using delivery = tuple<int, int, int>;
bool compare(delivery a, delivery b) {
if (get<1>(a) != get<1>(b)) return get<1>(a) < get<1>(b);
if (get<0>(a) != get<0>(b)) return get<0>(a) > get<0>(b);
return get<2>(a) > get<2>(b);
}
실제 문제 풀이에서는 위와 같은 비교 함수를 구현하였으나, 단순히 구간 길이를 뺄셈 연산으로 계산하여 비교하는 것이 더 직관적이다. 그렇게 구현하더라도 치명적인 결과 차이는 발생하지 않는다.
1
int *loaded_at = (int *)calloc(sizeof(int) * (N + 1));
트럭의 배송 한계를 고려하기 위해, 개별 구간마다 배송량을 추적할 필요가 있다. 위의 loaded_at[i]는 $i - 1$번 마을에서 $i$번 마을까지의 구간에서 적재된 택배 상자의 양을 기록하는데 사용한다.
각 구간에서 배송량을 선택하기 위해서는, 구간의 길이만큼 loaded_at 배열을 순회해야 한다. 하지만 시간이 지나치게 오래 걸리지는 않는다. 정렬에 의해서 구간이 길어질수록 반복 과정 상에서 더 늦게 처리되기 때문에, 앞서 선택된 구간들의 배송량에 의해 반복 과정이 조기에 종료되는 경우가 더 많아진다.
마무리
8980번 C++ 답안 - 생각을 완전히 정리하고 구현한 것이 아니어서 본문보다는 다소 복잡하게 구현되어있다.