백준 8980번 - 택배 (C++)

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

 

이 문제에서 떠올릴 수 있는 풀이법으로 처음에 배낭문제를 떠올렸다. 하지만 cost 와 value 를 나타낼 수 없었고 표가 그렇게 생긴 것 뿐이었다. 그래서 조금 더 고민하다가 떠오른 방법은 Greedy 였다.

 

이 문제는 대표적인 그리디 문제인 https://www.acmicpc.net/problem/1931 과 유사하다. 워딩은 다르지만 결국 택배를 많이 배달하기 위해선 가장 짧은 거리의 도착지에 도착해야한다. 회의실 배정 또한 가장 빨리 끝나는 회의를 담는 것과 같다.

그래서 이 문제는 회의실 배정에서 진행할 수 있는 회의의 갯수가 정해져있으며 동일한 회의를 중복하여 진행할 수 있는 문제로 바뀐다.

 

그러므로 회의실 배정과 같은 아이디어로 도착지가 작은 순으로 정렬하고, 출발지에서 가장 가까운 곳부터 택배를 싣는다. 문제 예제로 생각해보면

 

 

1번 마을에서 10 + 20 + 10을 싣는다. 여기서는 싣을수 있으면 무조건 전부내릴 수 있기 때문에 싣는 순간에 정답에 포함시킬 수 있다.

answer += 40

 

그리고 다음으로 이동한다. 2번 마을에선 3번마을과 4번 마을로 갈 수 있다. 그러나 막 실어선 안된다. 위에서 1번 마을~ 3번,4번 마을로 이미 배송중이기 때문에 사용할 수 있는 자리가 1번일 때 처럼 40이 아니다. 여기서 싣을 수 있는 최대 택배 수는 10개이다. 

 

answer += 10

 

이제 2번~ 4번 마을 배송을 처리하려해보면 지금 만석이라 더 싣을 수 없다. 넘어간다.

3번~4번 마을 배송을 처리해보자. 3번 마을로 배송하는 자리는 20자리가 남아있다. 그러므로 

 

answer += 20

 

정답은 70이다.

 

이것을 코드로 바꾸는 것도 여간 쉬운 문제는 아니었다. 코드로 변경하면 다음과 같다. 트럭 배열에 현재 담을 수 있는 택배의 개수를 저장해놓는 아이디어도 쉽지 않았다. 기업코테라면 킬러문제로 출제될 것 같다.

 

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

int N, C, M;
vector<pair<pair<int, int>, int>> info;

int truck[1000000] = {0,};

bool comp(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(){
	int answer = 0;
	cin >> N >> C >> M;

	for(int i = 0; i < M; i++){
		int a, b, c;
		cin >> a >> b >> c;
		info.push_back({{a, b},c});
	}

	sort(info.begin(), info.end(), comp);

	for(int i = 0; i < info.size(); i++){
		int from = info[i].first.first;
		int to = info[i].first.second;
		int box = info[i].second;
		int Max_Box = 0;

		for (int j = from; j < to; j++){
			Max_Box = max(Max_Box, truck[j]); // 1 -> 2 , 1 ->3 이면 1이 담을 수 있는 박스량이 정해져있음
		}

		int caps = min(box, C - Max_Box);

		for (int j = from; j < to; j++){
			truck[j] += caps;
		}

		answer += caps;
	}

	cout << answer << '\n';
}