8980번: 택배
입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이
www.acmicpc.net
필자는 이 문제를 보면서 백준의 회의실 배정, 강의실 배정과 비슷하다는 느낌을 받았다. 그 둘과 같이 이 문제도 그리디 문제이기 때문이다. 필자도 비전공자이며, 이론을 아주 탄탄하게 알고 있는 게 아니라서 그리디가 무엇인지 정확하게 설명하긴 어렵다. 하지만, 이 문제에 빗대서 대략적으로라도 풀어본다면, "트럭이 꽉 찼을 때, 가장 나중에 도착하는 마을로 배달하는 박스들부터 버린다"이다.
다른 사람들은 먼저 내리는 박스 순으로 정렬했는데, 필자는 (개인적으로는) 보다 직관적으로 먼저 방문하는 마을 순으로 정렬했다. 실제로 먼저 도착하는 마을에서 상차를 하기때문이다. 그리고 이제 경우에 따라 박스를 버려주면 되는 것이다.
배송기사가 트럭이 꽉 찼다고 함부로 박스를 버리면 안되겠지만...
어떻게 나중에 도착하는 마을로 가는 박스부터 버려야 가장 많은 박스를 배달할 수 있는 걸까?
필자가 생각한 부분은 '순환'이다. 최대한 빨리, 처리를 해버려야 이동 중간에 방문하는 마을로부터 새로운 박스를 받을 수도 있기 때문이다.
아래의 그림을 보자.
트럭의 상차 제한은 50,
1번에서 받아서 4번까지 가는 박스가 40개,
2번에서 3번까지 가는 박스 30개,
3번에서 4번까지 가는 박스 50개가 있다고 가정하자.
위와 같이, 마을 1에서는 40개가 상차된다. 다음 그림을 보자. 다음 그림이 이 문제의 거의 모든 걸 말해준다.
위에서 보면, 마을 2번에 도착하면 실어야 할 박스가 30개가 있는데, 이들은 3번 마을까지 가는 것들이다. 그리고 현재 공간은 10뿐이다.
여기서 곰곰이 잘 생각해보자. (우리는 가장 많은 박스를 배송해주기만 하면 된다. 누가 받든 상관없다)
4번 마을까지 가야 하는 박스 40개를 온전히 두고, 여기서 10개만 받을 수도 있다.
그런 식으로 진행하면,
3번 마을에 도착했을 때, 10개 배송 완료,
3번 마을에서 4번 마을까지 가는 새로운 박스 50개 중 10개만 상차.
4번 마을에 도착했을 때 상황은 1번에서 상차했던 박스 40개 + 3번에서 상차한 10개인 상태일 것이다.
그리고 이들을 모두 4번 마을에서 하차하여 50개를 배송 완료하게 된다.
총 배송 완료 개수는 60개이다.
하지만, 문제의 조건 중에 중요한 사항이 있다.
바로, "단, 받는 마을 번호는 보내는 마을 번호보다 항상 크다" 이 부분이다. 즉, 상차된 박스는 반드시 배송 완료된다. 그렇다면 당연히 일찍 배송을 완료시키는 게 낫지 않을까? 그래야 그만큼 트럭이 공간이 생겨 새 박스를 받을 수 있게 되니 말이다.
다시 위의 상황으로 돌아가서 생각해보면,
2번 마을에 도착했을 때, 1번에서 4번까지 가는 박스가 40개가 있지만, 2번에서 상차하는 박스는 3번에서 하차하므로 더 일찍 내릴 수 있다. 트럭 입장에서는 어차피 50개를 채우게 되는 상황인데, 기왕이면 일찍 하차하는 박스를 싣는 게 나은 것이다. 그래서 일찍 하차하는 박스가 우선순위를 갖게 되고, 빨간색으로 그린 부분처럼 4번 마을로 가는 박스 중 20개를 버리는 것이다.
바로 이 부분도 중요한데,
현재 트럭에 실려있는 박스들의 목적지를 보고, 가장 멀리 가는 박스부터 보는 것이다. 물론 현재 상차하려는 박스와 트럭 내 가장 멀리가는 박스의 목적지가 같다면, 버려서는 안된다. 어차피 버린만큼 실어서 똑같은 곳에 하차할텐데 왜 버리겠는가. 하지만 더 멀리가는 박스가 실려있을 때는, 그 박스를 최대한 버려주는 것이다.
트럭 내 박스는 마을 별로 정렬이 되어있고, 가장 멀리가는 마을부터 확인하며,
그 먼 마을로 가는 박스를 최대한 버려주고, 그러고도 모자라면 그다음 멀리 있는 마을 순으로 내려오면서 계속 버려주는 것이다.
다 버릴 것인지, 아니면 버릴 만큼만 버리고 (다 실을 수 있을 때까지) 상차할지 확인해주면 된다.
아래의 예시를 보자.
현재 트럭에는 2,3,4 마을로 가는 박스들이 각각 30,20,15개씩 실려있다. 현재 총 65개가 실려있고, 트럭의 박스 개수 제한은 70개라고 하자. 그리고 이번에 상차할 박스가 30개가 있는데, 이들의 목적지는 2이다.
이제 아래 그림을 보자.
현재 여유공간이 5 뿐이라서 (70-65) 30개를 실을 수 없다. 이 30개는 2번 마을까지 가므로 금방 하차한다. 그렇다면 최대한 순환을 일으키기 위해서는 당연히 2번 마을보다 멀리 가는 박스들을 버려야 한다! 그리고 그 순서는 가장 먼 마을부터 보는 것이다. 이번 예시에서는 4번 마을로 가는 박스부터 확인한다. 4번 마을로 가는 박스 15개를 모두 버려도 30개를 실을 수 없다. 그러므로 일단 15개를 모두 버린다!
이제 3번 마을까지 가는 박스를 보자. 이들은 20개를 트럭이 보유 중인데, 다 버릴 필요는 없다. 10개만 버려도 이번에 실어야 하는 30개를 모두 실을 수 있기 때문이다.
예시와 다르게 만약에 3번 마을로 가는 박스까지 모두 버려야 했다면 어떻게 될까?
물론 모두 버린다. 그러고 나서 2번 마을로 가는 박스들을 살펴봐야 하는데 이들은 이번에 실어야 하는 박스와 목적지가 같다. 그러므로 버릴 필요가 아예 없고, 실어야하는 박스 개수를 줄여서 상차하면 된다.
다시 정리하면,
- 순서대로 마을을 돌며, 상차를 해준다.
- 모두 다 실을 수 없을 때, 멀리 가는 마을부터 살펴본다.
- 모두 버려도 새 박스들을(목적지가 가까운) 다 실을 수 없다면 모두 버린다.
- 모두 버리지 않아도 된다면 최소한으로 버려준다.
- 만약 트럭에 실린 박스의 목적지와 새로 상차할 박스의 목적지가 같다면, 상차할 박스를 가능한 만큼만 싣는다.
<주요 내용>
그리디 알고리즘, 우선순위 큐
<코드>
필자는 처음에 트럭 내에 마을 번호별로 분류되는 배열을 만들고, 그 안에 벡터를 넣었다.
그리하여 먼 마을부터 확인할 때, 해당 벡터를 두고 루프를 돌아야 했다.
아래의 코드는 최적은 아니지만 AC를 받는 코드이다.
우선순위 큐를 통해 상차점 오름차순으로 정렬하고, (상차점이 같으면 도착점이 빠른 순)
먼저 현재 마을에서 하차를 완료한 후, 상차를 진행한다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define endl '\n'
using namespace std;
struct Box {
int a, b, c;
bool operator<(const Box &n) const {
if(a!=n.a)return a>n.a;
return b>n.b;
}
};
const int sz=2e3+1;
int mx,n,m,limit,hold,diff;
priority_queue<Box>pq;
vector<int>plans[sz];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin>>n>>limit>>m;
while(m--){
Box temp;
cin>>temp.a>>temp.b>>temp.c;
temp.c=min(limit,temp.c);
pq.push(temp);
}
for(int vn=1;vn<=n;++vn){
for(int&c:plans[vn]){
hold-=c;
mx+=c;
}
while(!pq.empty()&&pq.top().a<=vn){
Box curr=pq.top();pq.pop();
bool flag=0;
for(int v=n;v>curr.b && curr.c>(limit-hold);--v){
for(int&c:plans[v]){
diff=limit-hold;
if(curr.c<=diff){
flag=1;
break;
}
if(curr.c>diff+c){
hold-=c;
c=0;
}else{
hold-=curr.c-diff;
c-=curr.c-diff;
flag=1;
break;
}
}
if(flag)break;
}
if(curr.c>limit-hold)curr.c=limit-hold;
plans[curr.b].push_back(curr.c);
hold+=curr.c;
}
}
cout<<mx;
return 0;
}
아래의 코드는 보다 개선된 코드이다.
위의 코드에서는 마을 번호별로 박스들이 분류되어 벡터 안에 원소로 담겨있었는데,
생각해보면 그들을 모두 묶어주어도 된다. 어차피 같은 목적지에서 모두 하차하기 때문이다.
따라서 배열만 사용하고 벡터를 사용하지 않았다. 더 빨라졌다.
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#define endl '\n'
using namespace std;
struct Box {
int a, b, c;
bool operator<(const Box &n) const {
if(a!=n.a)return a>n.a;
return b>n.b;
}
};
const int sz=2e3+1;
int mx,n,m,limit,hold,diff;
priority_queue<Box>pq;
int plans[sz];
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL);cout.tie(NULL);
cin>>n>>limit>>m;
while(m--){
Box temp;
cin>>temp.a>>temp.b>>temp.c;
temp.c=min(limit,temp.c);
pq.push(temp);
}
for(int vn=1;vn<=n;++vn){
hold-=plans[vn];
mx+=plans[vn];
while(!pq.empty()&&pq.top().a<=vn){
Box curr=pq.top();pq.pop();
for(int v=n;v>curr.b && curr.c>(limit-hold);--v){
diff=limit-hold;
if(curr.c<=diff)break;
if(curr.c>plans[v]+diff){
hold-=plans[v];
plans[v]=0;
}else{
hold-=curr.c-diff;
plans[v]-=curr.c-diff;
break;
}
}
if(curr.c>limit-hold)curr.c=limit-hold;
plans[curr.b]+=curr.c;
hold+=curr.c;
}
}
cout<<mx;
return 0;
}
