[백준] 8980 - 택배

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

8980번: 택배

 

입력으로 들어오는 박스의 개수를 쪼갤 수 있어서 까다로운 문제였다.

핵심은, 도시는 1번부터 오름차순으로 방문, 즉 한 번 방문한 도시는 다시 방문하지 않기 때문에 1번 도시와 가까운 도시 순으로 박스를 옮기는 것이다.

1. 도착 도시 오름차순으로, 다음으로 출발 도시 오름차순으로 정렬한다.
2. 출발 도시와 도착 도시 사이를 체크하여 더 적재할 수 있는 최대 무게를 구한다.
3. 출발 도시와 도착 도시 사이에 더 적재할 수 있는 무게를 더한다.

 

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

typedef struct p {
	int start;
	int end;
	int box;
};

vector<p> v;
int can[2001];

bool compare(p& p1, p& p2) {
	if (p1.end == p2.end) {
		if (p1.start == p2.start) {
			return p1.box < p2.box;
		}
		return p1.start < p2.start;
	}
	return p1.end < p2.end;
}

int main() {
	int n, m, k;
	cin >> n >> m >> k;
	for (int i = 0; i < k; i++) {
		int a, b, c; cin >> a >> b >> c;
		v.push_back({ a,b,c });
	}
    
	sort(v.begin(), v.end(), compare);
	int ans = 0, weight = 0;
    
	for (int i = 0; i < k; i++) {
		int boxWeight = 0;
        
		for (int j = v[i].start; j < v[i].end; j++) {
			boxWeight = max(boxWeight, can[j]);
		}
        
		int leftSpace = min(v[i].box, m - boxWeight);
		ans += leftSpace;

		for (int j = v[i].start; j < v[i].end; j++) {
			can[j] += leftSpace;
		}
	}
	cout << ans;
}