택배(Greedy)

https://www.acmicpc.net/problem/8980

8980번: 택배

 

1. 배송 정보들을 받는 마을 기준으로 오름차순을 해준다.(받는 마을이 같다면 보내는 마을 기준)

2. 각 마을에서 박스를 얼마나 싣고있는지 저장할 리스트를 생성한다.

3. 2번의 리스트를 배송 정보의 시작지점~(끝지점-1)까지 탐색하여 얼마나 더 실을 수 있는지 탐색한다.

4. 더 실을 수 있다면 빈 공간과 비교하여 배송 정보의 박스값을 결과값에 추가한다.

5. 추가한 박스값만큼 3번에 탐색한 공간에 추가해준다.

6. 모든 배송 정보에 대하여 3~5번을 반복해준다.

 

시작 지점에서 가장 가까운 배송 정보를 선택해야 이후에 더 많은 택배를 실을 수 있다는 점에 유의해야 한다.

이러한 점 때문에 1번에서 받는 마을을 기준으로 오름차순을 해준 것이고

각 상황에서 가장 가까운 배송 정보를 선택하며 풀어나가기 때문에 그리디 알고리즘이라고 볼 수 있다.

 

보내는 마을	받는 마을	박스 개수
1	2	10
1	3	20
1	4	30
2	3	10
2	4	20
3	4	20

예시로 해당 과정을 직접 해보자

 

보내는 마을	받는 마을	박스 개수
1	2	10
1	3	20
2	3	10
1	4	30
2	4	20
3	4	20

먼저 받는 마을(같다면 보내는 마을) 기준으로 오름차순을 해준다

 

마을	1	2	3	4
박스 개수	0	0	0	0

각 마을마다 싣고있는 박스의 개수를 저장할 리스트를 만든다

 

시작: 1, 도착: 2, 박스: 10
마을	1	2	3	4
박스 개수	0 -> 10	0	0	0
결과: 0 -> 10

첫 번째 배송에 대한 탐색이다.

1~(2-1)에 대해서 탐색해야 하고 해당 지점에서 실을 수 있는 박스의 최대 개수는 40-0=40개다.

리스트와 결과값에 배송한 박스 10개를 추가한다.

 

시작: 1, 도착: 3, 박스: 20
마을	1	2	3	4
박스 개수	10 -> 30	0 -> 20	0	0
결과: 10 -> 30

두 번째 배송에 대한 탐색이다.

1~2번에서 실을 수 있는 박스의 최대 개수는 40-10=30개.

리스트와 결과값에 배송한 박스 20개를 추가.

 

시작: 2, 도착: 3, 박스: 10
마을	1	2	3	4
박스 개수	30	20 -> 30	0	0
결과: 30 -> 40

세 번째 배송에 대한 탐색이다.

2번에서 실을 수 있는 박스의 최대 개수는 40-20=20개.

리스트와 결과값에 10개를 추가.

 

시작: 1, 도착: 4, 박스: 30
마을	1	2	3	4
박스 개수	30 -> 40	30 -> 40	0 -> 10	0
결과: 40 -> 50

네 번째 배송에 대한 탐색이다.

1~3번에서 실을 수 있는 박스의 최대 개수는 40-30=10개.

리스트와 결과값에 10개를 추가.

 

시작: 2, 도착: 4, 박스: 30
마을	1	2	3	4
박스 개수	40	40	10	0
결과: 50

다섯 번째 배송에 대한 탐색이다.

2~3번에서 실을 수 있는 박스의 최대 개수는 40-40=0개.

해당 배송정보의 박스는 실을 수 없다.

 

시작: 3, 도착: 4, 박스: 20
마을	1	2	3	4
박스 개수	40	40	10 -> 30	0
결과: 50 -> 70

여섯 번째 배송에 대한 탐색이다.

3번에서 실을 수 있는 박스의 최대 개수는 40-10=30개.

리스트와 결과값에 20개를 추가.

 

이렇게 해서 최대 70개를 배송할 수 있다는 결과가 나오게 된다.

 

#include <iostream>
#include <queue>
using namespace std;

int village[2001] = { 0, };

class Info
{
public:
	int s;
	int d;
	int box;
	Info(int s, int d, int box)
	{
		this->s = s;
		this->d = d;
		this->box = box;
	}
	bool operator<(const Info& i) const
	{
		if (this->d == i.d) return this->s > i.s;
		else return this->d > i.d;
	}
};

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int n, c;
	cin >> n >> c;

	int cmd;
	cin >> cmd;
	priority_queue<Info> pq;
	while (cmd--)
	{
		int s, d, b;
		cin >> s >> d >> b;
		pq.push(Info(s, d, b));
	}

	int ret = 0;
	while (!pq.empty())
	{
		Info info = pq.top();
		pq.pop();
		int maxw = 0;
		for (int i = info.s; i < info.d; i++)
		{
			if (village[i] > maxw) maxw = village[i];
		}
		int payload = (info.box > c - maxw) ? c - maxw : info.box;
		for (int i = info.s; i < info.d; i++)
		{
			village[i] += payload;
		}
		ret += payload;
	}

	cout << ret << '\n';
}