택배
알고리즘 구분 : 그리디
문제
아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽으로 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
문제 풀이
문제 풀이를 할 때, 총 3가지의 방법을 시도하게 되었다. 마지막 방법은 도움을 좀 받아서 풀게 되었다.
1) 1 -> N까지의 마을로 이동하는 과정에서 해당 위치에서 가장 많은 양의 택배를 실어서 전달하는 방법
위 방법은 해당 마을에서 담을 수 있는 택배를 최대한으로 담는 방식의 그리디를 취했었다. 그러나, 이 방법으로는 예제 2번을 해결할 수 없었다.
void solve() {
int capacity = 0; // 트럭 용량
int result = 0;
for(int i = 1; i < n + 1; i++) {
cout << i << " " << truck[i] << " " << capacity << endl;
// 택배 내리기
if(truck[i] != 0) {
capacity -= truck[i];
result += truck[i];
}
// 보내야 될 택배 담기
for(auto now : box[i]) {
if(capacity < c) {
if(now.second <= c - capacity) {
capacity += now.second;
truck[now.first] += now.second;
}
else {
truck[now.first] = c - capacity;
capacity = c;
}
}
}
}
cout << result << endl;2) N -> 1까지의 마을로 역순으로 이동하며 해당 위치에서 내릴 수 있는 가장 많은 양의 택배를 싣는 방법
위 방법은 마을을 역순으로 돌며 해당 위치에 내릴 수 있는 택배를 최대한으로 담는 방식의 그리디였으나, 11%에서 WA 판정을 받았다.
void solve() {
int result = 0;
int capacity = 0; // 트럭 용량
// N번 마을 to 1번 마을
for(int i = n; i > 0; i--) {
if(capacity != 0) {
capacity -= truck[i];
result += truck[i];
}
while(!box[i].empty()) {
int cost = box[i].top().first;
int start = box[i].top().second;
box[i].pop();
if(capacity < c) {
if(cost <= c - capacity) {
capacity += cost;
truck[start] += cost;
}
else {
truck[start] = c - capacity;
capacity = c;
}
}
else {
break;
}
}
}
cout << result << endl;
}3) 도착지점을 기준으로 정렬하여 택배가 지나가는 길 배열을 생성하여 그리디하게 취하는 방법
예제 1번을 기준으로 쉽게 설명하자면
(1) 도착지점을 기준으로 택배를 정렬
1 2 10
1 3 20
2 3 10
1 4 30
2 4 20
3 4 20
(2) 트럭이 마을을 지나가는 길별 용량을 확인
0 0 0 01 2 10
10 0 0 0
택배 10 탑재1 3 20
30 20 0 0
택배 20 탑재2 3 10
30 30 0 0
택배 10 탑재1 4 30
30 30 0 0
용량 부족으로 탑재 X2 4 20
30 30 0 0
용량 부족으로 탑재 X3 4 20
30 30 20 0
택배 20 탑재
--> 탑재 용량을 다 더하면 10 + 20 + 10 + 20 = 70
Result : 70
위와 같은 과정으로 진행되도록 구현하면 된다.
소스 코드
#include <bits/stdc++.h>
using namespace std;
#define endl "\n"
int n, c, m;
vector<pair<pair<int, int>, int>> box;
int truck[2001];
bool compare(const pair<pair<int, int>, int> &a, const pair<pair<int, int>, int> &b); //first.first : start, first.second : dest, second : count
void solve();
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
memset(truck, 0, sizeof(truck));
cin >> n >> c >> m;
for(int i = 0; i < m; i++) {
int a, b, c;
cin >> a >> b >> c;
box.push_back({{a, b}, c});
}
solve();
return 0;
}
bool compare(const pair<pair<int, int>, int> &a, const pair<pair<int, int>, int> &b) {
if(a.first.second == b.first.second) {
return a.first.first < b.first.first;
}
return a.first.second < b.first.second;
}
void solve() {
int result = 0;
sort(box.begin(), box.end(), compare);
for(auto now : box) {
int maxBox = 0;
int start = now.first.first;
int dest = now.first.second;
int capacity = now.second;
for(int i = start; i < dest; i++) {
maxBox = max(maxBox, truck[i]);
}
maxBox = min(c - maxBox, capacity);
result += maxBox;
for(int i = start; i < dest; i++) {
truck[i] += maxBox;
}
}
cout << result << endl;
}- 문제 출처 : https://www.acmicpc.net/problem/8980
- 해당 풀이는 백준에서 "맞았습니다!!" 판정을 받았습니다.
