백준 No.8980 [택배]

Baekjoon Online Judge No.8980 [택배]

---

  문제 

8980번: 택배 (acmicpc.net)

8980번: 택배

---

  설명 

<알고리즘 분류>
   * 그리디 알고리즘 (Greedy algorithm)
   * 정렬 (Sorting)

 

  그리디 알고리즘을 통해 풀 수 있는 문제이다. 그리디 알고리즘으로 이 문제를 푼다면? 택배차는 되는만큼 박스를 싣는다고 생각하면 된다. 단, 택배차의 최대 적재 개수가 있으므로 그 적재 개수를 고려하면서 되는만큼 실어야 한다.

 

  잘 생각을 해 보면, 이러한 것들을 고려해볼까 생각해볼 수 있다.

1. 택배를 오래 싣고 가면, 즉 첫 번째 마을에서 끝 마을 가깝게 택배를 싣고 간다면,
     그만큼 그 동선에서 실을 수 있는 박스의 양에 영향을 받는다.
2.  그렇다고 경유지가 적은 택배들 순으로 적재 / 배송 한다면 반례가 많이 존재할 것 이다.
3.  고로, 머리가 좀 아프다.

 

  이러한 것들을 고려하면 우선 택배들의 리스트를 도착지 오름차순으로 정렬을 해 놓는 편이 좋다. 도착지가 오름차순이면 도착지가 가까운 택배 순으로 처리하여 결국 경유지자 적기 때문이다. 그리고, 도착지가 같은 택배 리스트들은 도착지가 같은 택배 리스트들 끼리 출발지를 오름차순으로 정렬을 한다.

 

  도착지가 같은 택배 리스트들 끼리 출발지를 오름차순으로 정렬하는 이유는? 

 

  1, 2, 3, 4 번째 마을에서 모두 5 번째 마을로 택배를 보내야 하는 상황이다. 이 경우에는 어쨌든 차에 언제 어떻게 적재를 하던 결국 다 5번째 마을에서 하차를 하게 된다. 그러니 앞 마을서부터 차례대로 먼저 적재하는 경우가 5 번 마을에서 하차하는 박스의 수는 누적되어 제일 많은 박스를 하차할 경우가 많을 것 이다.

  그렇다면, 이 다음으론 이제  6번 이상의 마을들에 대한  문제를 생각해 볼 수 있다.  6번 이상의 마을들에 대한 배송을 고려할 땐 사실 위 그림에서 어떻게 배송을 하던 결국 4번 마을에서 되는만큼 실었을 것 이기 때문에 {1, 2, 3, 4} 번 마을에서 6번 이상의 마을에 배송을 하는 경우는 많이 없을 것 이다.

  따라서, 결론적으론? 우선순위큐를 이용하여 목적지를 오름차순으로, 목적지가 같은 경우엔 출발지를 오름차순으로 정렬을 하여 계속해서 되는만큼 실으면 된다. 그리고, 어느 마을에서 다른 마을로 가는 택배를 적재할 땐 그 마을로 가면서 있을 중간 경유지들 중의 최대 택배 적재 예약(?)양을 확인하여 적재를 해야한다.

---

  Code 

#include <iostream>
#include <vector>
#include <queue>

using namespace std;

struct Coupang {
	int s, e; // 현재 택배의 시작지역 / 도착지역
	int w;	  // 현재 택배의 박스 수
};

struct comp {
	// 도착 지점을 오름차순으로 정렬하고,
	// 도착 지점이 같을 땐 출발 지점을 오름차순으로 정렬
	bool operator()(Coupang a, Coupang b) {
		if (a.e < b.e) return false;
		else if (a.e > b.e) return true;
		else if (a.e == b.e) {
			if (a.s < b.s) return false;
			else return true;
		}
	}
};

priority_queue<Coupang, vector<Coupang>, comp> pq;
vector<int> storage;
int n, limit, load;

int main() {
	ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	cin >> n >> limit >> load;

	storage.assign(n + 1, 0);

	int from, to, w;
	while (load--) {
		cin >> from >> to >> w;

		pq.push({ from, to, w });
	}

	int answer = 0;
	int curBoxCount = 0;
	int leftStorage = 0;

	while (!pq.empty()) {
		Coupang cur = pq.top();
		pq.pop();

		curBoxCount = 0;

		for (int i = cur.s; i < cur.e; i++) // 현재 택배의 출발 ~ 끝 전 범위에서 박스가 가장 많이 있는 정도를 체크
			curBoxCount = max(curBoxCount, storage[i]);

		leftStorage = min(cur.w, limit - curBoxCount); // 현재 박스를 실을 수 있는 만큼 상차
		answer += leftStorage; // 상차 한 만큼 answer 에 추가한다.

		for (int i = cur.s; i < cur.e; i++) // 지금 실은 택배만큼 이 택배가 경유하는 모든 곳에 체크를 해 놓는다.
			storage[i] += leftStorage;
	}

	cout << answer;
}

---

  고찰 

  알고리즘 공부를 시작한 처음에는 그리디 알고리즘에 대해서 그냥 되는만큼 처음부터 최대한 다 챙겨가기만 하면 되는 알고리즘으로 생각해서, 별로 어렵지 않을거라는 생각을 하였었다. 그런데 아니다. 어느 상황에 그리디 알고리즘을 활용하여 최대한 혹은 최소한 챙겨야 할 지 판단하고 이렇게 한 경우 다음 경우들은 어떠한 영향을 받는지 등 구조적으로 각 경우들에 대한 서로의 관계를 파악해야 하는 것이 생각보다 많은 생각을 요구하는 것 같다.