[백준 8980번 C/C++] 택배

 

[백준 8980번 C/C++] 택배

 

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

 

8980번: 택배

입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이

www.acmicpc.net

---

 

 

해결전략

 

그리디 Greedy Algorithm

 

1. 각 택배를 가능한 한 먼저 배달해야 하는 목적지 마을 순으로 정렬.
2. 각 마을별 남은 용량 계산
   • 트럭이 각 마을을 방문할 때마다 특정 용량만큼의 박스를 싣고 내린다. 
   • 이를 관리하기 위해 capacity 벡터를 사용하여 각 마을별로 남은 용량을 관리한다. 초기값은 트럭의 최대 용량인 c로 설정한다.
3. 택배 배달
   • 각 택배에 대해 시작 마을부터 목적지 마을까지의 경로에 대해 현재 남아 있는 최소 용량을 찾는다. 
   • 해당 택배가 이 경로를 거치며 최대로 실을 수 있는 박스의 수를 결정한다.
   • 이 최소 용량(minCap)과 택배의 박스 수(v[i].box) 중 더 작은 값이 실제로 이번에 실을 수 있는 박스의 수(canLoad)가 된다.
   • 이 canLoad만큼 각 마을의 capacity를 감소시킨다.
   • answer에도 canLoad를 더하여 최종적으로 배달할 수 있는 박스의 총 개수를 계산한다.

 

각 택배를 운반하는 과정에서 경로 상의 모든 마을에서 남은 용량 중 최소값을 찾아 그만큼만 운반 시킨다. 

 

 

 

핵심 아이디어

• 효율적인 배달 순서: 목적지 마을 번호가 낮은 순서대로 택배를 정렬하고 배달함으로써, 트럭의 이동 경로를 최적화하고, 중간에 다른 택배를 추가로 실을 수 있는 기회를 최대화한다.
• 경로 상의 최소 용량을 기준으로 택배를 싣는 방법: 각 마을별로 남은 용량을 최적으로 관리하면서, 가능한 많은 택배를 목적지까지 운반할 수 있다.

 

---

 

 

정답코드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int n, c;	// n: 마을의 수, c: 트럭의 용량
int m;		// m: 보내는 박스의 개수
int answer; // 최종적으로 배달할 수 있는 박스의 총 개수
 
struct Info {
	int start, end, box; // 시작 마을, 목적 마을, 택배의 박스 개수
 
	Info(int a, int b, int c) {
		start = a;
		end = b;
		box = c;
	}
 
	// 목적 마을이 낮은 순으로 정렬! 그 다음에 시작 마을 낮은 순 정렬
	bool operator<(const Info& oper) {
		if (end == oper.end) {
			start < oper.start;
		}
		return end < oper.end;
	}
};
 
vector<Info> v;
 
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
 
	cin >> n >> c >> m;
	for (int i = 0; i < m; i++) {
		int a, b, c;
		cin >> a >> b >> c;
		v.push_back({ a, b, c });
	}
	sort(v.begin(), v.end()); // 목적 마을이 낮은 순으로 정렬! 그 다음에 시작 마을 낮은 순 정렬
 
 
	vector<int> capacity(n + 1, c); // 각 마을별 남은 용량. 기본값 최대 용량인 c로 설정
 
	for (int i = 0; i < v.size(); i++)
	{
		// 시작 마을부터 목적지 마을까지의 경로에서 현재 남아 있는 최소 용량을 찾는다. 
		// 이 최소 용량과 해당 택배의 박스 개수 중 더 작은 값이 이번에 실을 수 있는 박스의 수(canLoad)가 된다.
		int minCap = c;
		for (int j = v[i].start; j < v[i].end; j++) {
			minCap = min(minCap, capacity[j]);
		}
 
		// 시작 마을부터 목적지 마을 전까지의 각 마을의 남은 용량을 canLoad만큼 감소시킨다. 
		// 해당 택배가 해당 경로를 거치며 운반되고 있음
		int canLoad = min(minCap, v[i].box);
		for (int j = v[i].start; j < v[i].end; j++) {
			capacity[j] -= canLoad;
		}
 
		answer += canLoad;
	}
 
	cout << answer;
 
	return 0;
}

 

 

---