대엉코딩

www.acmicpc.net/problem/8980

1. 풀이방법

 - 그리디 문제인데 매우 까다로웠다...

 - 처음에 문제의 설명 방식대로 구현을 하다 보면 반례도 잘 떠오르지 않고 매우 어려웠다...

 - 결국 참고한 게시판의 답변입니다

   (www.acmicpc.net/board/view/6327) 게시판의 plzrun 님의 답변을 보면

 - 왜 도착지를 기준으로 정렬을 해야하는 지를 잘 알 수 있다.

 - 처음 구현한 것도 앞마을 부터 차례대로 박스를 올리는데 뭐가 틀렸지? 를 한참 생각했지만...

 - 문제점은 출발마을을 앞부터 차례대로 기준으로 삼으며 도착지가 가까운 마을 부터 박스를 올린 것이다.

 - 핵심은 1,2,3,... 시작마을부터 차례대로 살피는게 아닌 무조건 도착지가 앞 쪽인 택배박스 부터 올려야 최대의

   양을 배달 할 수 있다.

2. 주의사항

 - 위의 것을 깨닫고도 구현을 생각하는 것도 꽤나 까다로웠습니다..(저는...ㅠㅠ)

 - 문제의 시작부터 마을을 살피는 것으로 생각해서 그 생각에서 벗어나기가;;;

 - 결국 해결한 것은 마을에서의 트럭의 가용용량을 배열로 선언해 저장하고, 박스들을 살펴가며

   마을 별 가용용량을 조절해주는 식으로 구현하였습니다.

3. 나의코드

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

struct box {
	int start;
	int end;
	int weight;
};
int N,C; //마을의 수 , 트럭의 용량
int M; // 박스정보의 수
int x, y, weight;
int result;
int truck[2001]; //마을 별 트럭의 공간을 표시하기 위해서 (트럭에 올라가있는 박스의 상태)

bool compare(box &lhs, box &rhs) {
	if (lhs.end < rhs.end) return true;
	else if (lhs.end == rhs.end) {
		if (lhs.start <= rhs.start) return true;
		else return false;
	}
	else return false;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	cin >> N >> C; //마을 수 와 트럭의 용량
	cin >> M;
	vector<box> sendbox(M);
	for (int i = 0; i < M; i++) {
		cin >> sendbox[i].start >> sendbox[i].end>>sendbox[i].weight;
	}
	sort(sendbox.begin(), sendbox.end(), compare);

	for (int i = 0; i < M; i++) {
		int cnt = 0;
		for (int j = sendbox[i].start; j < sendbox[i].end; j++) {
			cnt = max(truck[j], cnt);
		}
		result += min(sendbox[i].weight, C - cnt); //박스를 올리자 (담을 수 있는 양이 더 적으면 그 만큼만 올릴 수 있다)
		for (int j = sendbox[i].start; j < sendbox[i].end; j++) { //그 만큼 지나가는 마을에서의 트럭의 용량에서 빼줌
			truck[j] += min(sendbox[i].weight, C - cnt);
		}
	}
	cout << result << "\n";
	return 0;
}