C++ / 백준 / 8980 / 택배

문제

 

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

8980번: 택배

문제풀이

 

다 풀고 다른 분들의 풀이를 봤는데 간단하게 풀으셨다...

이런 풀이도 있다 참고만 하시는 걸로...

마을 1부터 마을 N까지 탐색하면서 마을에 도착하면 내릴 수 있는 박스 다 내리고, 박스를 싣는다.

박스를 실을 때는 최대 용량보다 적게 싣는다.

만약 용량을 넘어서면 이전에 실은 박스 중에서 도착 마을이, 이번에 실을 박스의 도착지 보다 먼 마을이 있으면, 박스를 교체하는 식으로 코드를 작성했다.

 

town1은 박스를 싣는 마을, town2는 도착 마을, town1_box는 town1에서 박스를 실을 수 있는 개수, loaded_box는 트럭에 담긴 박스 개수 변수이다.

 

vector<vector<pair<int, int>>>box로 box[싣는 마을1].{도착 마을, 박스 개수} 이렇게 나타냈다.

box는 싣는 마을이 작은 순, 도착마을이 큰 순으로 정렬한다.

map<int, int, greater<int>>m, 맵을 이용 해 트럭에 실은 박스 상태를 나타낼 것이다.

맵에는 도착 마을, 실은 박스의 정보만 담을 것이다.

정렬은 내림차순으로 하여 도착마을이 먼 마을이 앞에 오도록 했다.

 

	for (town1 = 1; town1 <= N; ++town1) {
		answer += m[town1];
		loaded_box -= m[town1];
		auto iter = m.find(town1);
		m.erase(iter);

이번 마을에서 내린 박스 양만큼 답에 더하고, 트럭에 담긴 박스 개수에서는 빼고, m에선 지운다.

 

for (idx = 0; idx < box[town1].size(); ++idx) {
			town2 = box[town1][idx].first;
			town1_box = box[town1][idx].second;

			if (loaded_box + town1_box <= C) {
				loaded_box += town1_box;
				m[town2] += town1_box;
			}

실을 수 있는 박스 + 트럭에 있는 박스가 용량이하라면 박스를 다 실는다.

 

		else if (loaded_box + town1_box > C) {
				m[town2] += max(0, C - loaded_box);
				town1_box -= max(0, C - loaded_box);
				loaded_box = C;

				for (auto iter = m.begin(); iter != m.end();) {
					if (town1_box == 0) break;
					if (town2 < iter->first) {
						if (town1_box <= iter->second) {
							m[town2] += town1_box;
							iter->second -= town1_box;
							town1_box = 0;
						}
						else if (town1_box > iter->second) {
							m[town2] += iter->second;
							town1_box -= iter->second;
							m.erase(iter++);
						}
					}
					else {
						break;
					}
				}
			}

박스가 용량을 넘어갈 경우이다.

일단 실을 수 있는 박스를 용량까지 싣는다.

남는 박스는 이미 실어져 있는 m을 탐색하면서 더 효율적으로 배송할 수 있는 박스를 찾는다.

(만약 마을 1에서 마을 10으로 박스가 100개 있고, 새로 실을 수 있는 박스는 마을 5에 내릴 박스라면 효율이 더 좋으므로 교체를 해야 한다.)

 

박스를 교체했는데도 실을 수 있는 박스가 더 있으면 맵의 다음을 탐색해서 똑같이 한다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

bool cmp(pair<int, int>box1, pair<int, int>box2) {
	if (box1.first == box2.first) {
		return box1.second < box2.second;
	}
	return box1.first < box2.first;
}

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

	int N(0), C(0), M(0), idx(0), cnt(0), answer(0);
	int town1(0), town2(0), town1_box(0), loaded_box(0);

	cin >> N >> C >> M;
	vector<vector<pair<int, int>>>box(N + 1);
	map<int, int, greater<int>>m;

	for (idx = 0; idx < M; ++idx) {
		cin >> town1 >> town2 >> cnt;
		box[town1].push_back({ town2, cnt });
	}

	for (idx = 1; idx <= N; ++idx) {
		sort(box[idx].begin(), box[idx].end(), cmp);
	}

	for (town1 = 1; town1 <= N; ++town1) {
		answer += m[town1];
		loaded_box -= m[town1];
		auto iter = m.find(town1);
		m.erase(iter);

		for (idx = 0; idx < box[town1].size(); ++idx) {
			town2 = box[town1][idx].first;
			town1_box = box[town1][idx].second;

			if (loaded_box + town1_box <= C) {
				loaded_box += town1_box;
				m[town2] += town1_box;
			}
			else if (loaded_box + town1_box > C) {
				m[town2] += max(0, C - loaded_box);
				town1_box -= max(0, C - loaded_box);
				loaded_box = C;

				for (auto iter = m.begin(); iter != m.end();) {
					if (town1_box == 0) break;
					if (town2 < iter->first) {
						if (town1_box <= iter->second) {
							m[town2] += town1_box;
							iter->second -= town1_box;
							town1_box = 0;
						}
						else if (town1_box > iter->second) {
							m[town2] += iter->second;
							town1_box -= iter->second;
							m.erase(iter++);
						}
					}
					else {
						break;
					}
				}
			}
		}
	}
	cout << answer;
}