백준 8980 : 택배 C++

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

8980번: 택배

원래 보내는곳 순으로 정렬한 후

queue를 활용한 시뮬레이션으로 돌리려 했지만, 자꾸 틀려서 다른 분 풀이를 참고했다.

 

풀이

1. 우선 일거리들을 도착 빠른 순으로 정렬

 

2. 출발지부터 도착지 - 1 까지 잔여용량이 가장 적은 곳 찾기

 

3. 실을 박스의 수 정하기

 -> 용량초과일 수도 있으니

4. 출발지부터 도착지 - 1 까지 실을 박수의 수만큼 잔여용량을 줄여주기

 

 

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

struct box {
	int from;
	int to;
	int num;
};

bool cmp( box a, box b )
{
	return a.to < b.to;
}

int n,c,m;
int in1, in2, in3;
int answer = 0;
vector<box> boxes;

int main()
{
	//n 마을 수, c 트럭 용량
	cin >> n >> c;
	cin >> m;

	vector<int> left(n + 1, c);

	for (int i = 0; i < m; i++)
	{
		cin >> in1 >> in2 >> in3;
		boxes.push_back({ in1,in2,in3 });
	}

	sort(boxes.begin(), boxes.end(),cmp);

	for (int i = 0; i < m; i++)
	{
		//가능 경로에서 최대로 실을 수 있는 것들
		int mini = left[boxes[i].from];
		for (int j = boxes[i].from + 1; j < boxes[i].to ; j++)
		{
			mini = min(mini, left[j]);
		}

		int cnt = boxes[i].num;
		if (mini < cnt)
			cnt = mini;
		answer += cnt;

		for (int j = boxes[i].from; j < boxes[i].to; j++)
		{
			left[j] -= cnt;
		}
	}
	cout << answer << endl;

	return 0;
}