[백준] 8980번 : 택배 (C++)

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

8980번: 택배

이 문제에서의 핵심은 택배를 올리면 무조건 목적지에서 내려지기 때문에 무게 맞게 올리는 경우만 고려하면된다.

따라서, 받는 마을과 보내는 마을의 차이가 작고, 택배를 빨리 내릴수록 효율적이기 때문에 받는 마을의 번호를 기준으로 오름차순 정렬한 후 탐색해야한다.

 

오랜만에 다시 본 문제였는데도 풀이방식이 제대로 생각나지 않았다... 몇번 더 풀어봐야 할 것같다! 

 

문제 풀이 방식은 다음과 같다.

1. 받는 마을의 번호를 기준으로 오름차순 정렬한다.

2. 정렬 된것을 앞에서 부터 탐색한다. 이 때, A에서 출발해서 B에서 내리는 택배가 있다고 하면 A, A+1, ..., B-1까지 해당 택배의 무게 여유 공간이 있어야 한다. 따라서, A~B-1 중 가장 많은 싣고있는 택배의 크기를 구하고 이걸 max_truck이라는 변수에 담아논다.

3.  min(현재 택배 무게, 트럭 용량 - max_truck) 을 통해 올릴 수 있는 택배 무게인 capacity를 구한다. 이렇게 하는 이유는 현재 택배 무게보다 남은 용량이 작다면 다 싣을수 없기 때문이다!

4. A~B-1 공간에 모두 capacity만큼 더해준다.

 

성공적으로 싣은 택배의 무게합을 구하기 위해 success변수에 계속해서 capacity를 누적시키는 방법을 사용하였다.

 

전체코드는 아래와 같다 :) 

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

//핵심: 택배 내리는 상황은 고려x(무게맞게 싣으면 무조건 내리기 때문에) 대신에 각 마을에서 트럭이 싣고있는 택배의 개수만 고려
//		받는 마을의 번호를 기준으로 오름차순 정렬(받는마을과 보내는마을의 차이가 작을수록 효율적)

int N, C; //마을 수, 트럭용량
int M; //박스 정보개수
vector<pair<pair<int, int>, int>> list; //택배 <<보내는마을,받는마을>,박스개수>
int truck[2001]; //마을별로 트럭에 싣고있는 택배개수 저장
int success; //최대 박스수

bool compare(pair<pair<int, int>, int> a ,pair<pair<int, int>, int> b) { //받는마을 기준으로 오름차순 정렬
	if (a.first.second == b.first.second) return a.first.first < b.first.first;
	else return a.first.second < b.first.second;
}

int main() {
	cin >> N >> C;
	cin >> M;

	for (int i = 0; i < M; i++){
		int sender, receiver, box;
		cin >> sender >> receiver >> box;
		list.push_back({ {sender,receiver},box });
	}
	sort(list.begin(), list.end(),compare);

	for (int i = 0; i < list.size(); i++){
		int from = list[i].first.first; //출발
		int to = list[i].first.second; //도착
		int size = list[i].second; //싣어야할 택배수
		int max_truck= 0; //현재 택배가 지나가야할 truck배열값중 가장큰거
		for (int j = from; j < to; j++){
			max_truck = max(truck[j], max_truck);
		}
		int capacity = min(size,C-max_truck);//가져갈수있는 택배수 구하기위한 변수 (원래 택배수,가능한공간)
		for (int j = from; j < to; j++) { //출발부터 도착전까지 가능한 택배수 할당
			truck[j] += capacity;
		}
		success += capacity; //트럭에 성공적으로 싣은 택배
	}
	cout << success;
}