BOJ 8980 - 택배

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	128 MB	4127	1391	1023	35.882%

문제

---

아래 그림과 같이 직선 도로상에 왼쪽부터 오른쪽으로 1번부터 차례대로 번호가 붙여진 마을들이 있다. 마을에 있는 물건을 배송하기 위한 트럭 한 대가 있고, 트럭이 있는 본부는 1번 마을 왼쪽에 있다. 이 트럭은 본부에서 출발하여 1번 마을부터 마지막 마을까지 오른쪽으로 가면서 마을에 있는 물건을 배송한다.

각 마을은 배송할 물건들을 박스에 넣어 보내며, 본부에서는 박스를 보내는 마을번호, 박스를 받는 마을번호와 보낼 박스의 개수를 알고 있다. 박스들은 모두 크기가 같다. 트럭에 최대로 실을 수 있는 박스의 개수, 즉 트럭의 용량이 있다. 이 트럭 한대를 이용하여 다음의 조건을 모두 만족하면서 최대한 많은 박스들을 배송하려고 한다.

• 조건 1: 박스를 트럭에 실으면, 이 박스는 받는 마을에서만 내린다.
• 조건 2: 트럭은 지나온 마을로 되돌아가지 않는다.
• 조건 3: 박스들 중 일부만 배송할 수도 있다.

마을의 개수, 트럭의 용량, 박스 정보(보내는 마을 번호, 받는 마을번호, 박스 개수)가 주어질 때, 트럭 한 대로 배송할 수 있는 최대 박스 수를 구하는 프로그램을 작성하시오. 단, 받는 마을번호는 보내는 마을번호보다 항상 크다.

예를 들어, 트럭 용량이 40이고 보내는 박스들이 다음 표와 같다고 하자.

보내는 마을	받는 마을	박스 개수
1	2	10
1	3	20
1	4	30
2	3	10
2	4	20
3	4	20

이들 박스에 대하여 다음과 같이 배송하는 방법을 고려해 보자.

(1) 1번 마을에 도착하면

다음과 같이 박스들을 트럭에 싣는다. (1번 마을에서 4번 마을로 보내는 박스는 30개 중 10개를 싣는다.)

보내는 마을	받는 마을	박스 개수
1	2	10
1	3	20
1	4	30

(2) 2번 마을에 도착하면

트럭에 실려진 박스들 중 받는 마을번호가 2인 박스 10개를 내려 배송한다. (이때 트럭에 남아있는 박스는 30개가 된다.)

그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 40개가 된다.)

보내는 마을	받는 마을	박스 개수
2	3	10

(3) 3번 마을에 도착하면

트럭에 실려진 박스들 중 받는 마을번호가 3인 박스 30개를 내려 배송한다. (이때 트럭에 남아있는 박스는 10개가 된다.)

그리고 다음과 같이 박스들을 싣는다. (이때 트럭에 실려 있는 박스는 30개가 된다.)

보내는 마을	받는 마을	박스 개수
3	4	20

(4) 4번 마을에 도착하면

받는 마을번호가 4인 박스 30개를 내려 배송한다

위와 같이 배송하면 배송한 전체 박스는 70개이다. 이는 배송할 수 있는 최대 박스 개수이다.

입력

---

입력의 첫 줄은 마을 수 N과 트럭의 용량 C가 빈칸을 사이에 두고 주어진다. N은 2이상 2,000이하 정수이고, C는 1이상 10,000이하 정수이다. 다음 줄에, 보내는 박스 정보의 개수 M이 주어진다. M은 1이상 10,000이하 정수이다. 다음 M개의 각 줄에 박스를 보내는 마을번호, 박스를 받는 마을번호, 보내는 박스 개수(1이상 10,000이하 정수)를 나타내는 양의 정수가 빈칸을 사이에 두고 주어진다. 박스를 받는 마을번호는 보내는 마을번호보다 크다.

출력

---

트럭 한 대로 배송할 수 있는 최대 박스 수를 한 줄에 출력한다.

접근

---

재미있는 방식의 그리디 문제였다.
이러한 문제에서는 어떻게 정렬하는가가 가장 중요하다.
본 문제에서는 도착도시를 기준으로 정렬하는 것이 핵심이다.

N의 최댓값이 2000이므로, O(N²)의 시간복잡도를 가져도 충분하다.
따라서, 시작점 ~ 도착점 까지의 박스 적재수를 확인하면서 순회해도 괜찮았다.

풀이

---

우선 도착 도시를 기준으로 오름차순 정렬하기 위해 pq에 넣어주었다.
각 노드마다 시작점 ~ 도착점 - 1 값의 box 수를 세서 가장 큰 값을 cnt에 저장했다.
그리고 다시 순회하면서 더 넣을 수 있는 최댓값을 num에 저장했다.
num을 ans에 더해주고, 다시 순회하면서 box에 num을 더해주면 된다.

#include <bits/stdc++.h>
using namespace std;
#define ll long long int
#define FUP(i, a, b) for(int i = a; i <= b; i++)
#define FDOWN(i, a, b) for(int i = a; i >= b; i--)
#define MS(a, b) memset(a, b, sizeof(a))
#define ALL(v) v.begin(), v.end()
#define CIN(a) cin >> a;
#define CIN2(a, b) cin >> a >> b
#define CIN3(a, b, c) cin >> a >> b >> c
#define COUT(a) cout << a
#define COUT2(a, b) cout << a << ' ' << b
#define COUT3(a, b, c) cout << a << ' ' << b << ' ' << c
#define ENDL cout << '\n'
int dy[4] = { -1, 1, 0, 0 };
int dx[4] = { 0, 0, 1, -1 };
#define piii pair<pair<int, int>, int>


int N, C, M, a, b, c, box[2001], ans = 0;

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	MS(box, 0);
	CIN3(N, C, M);
	priority_queue<piii, vector<piii>, greater<piii>> pq;
	while (M--)
	{
		CIN3(a, b, c);
		pq.push({ {b, a}, c });
	}
	while (!pq.empty())
	{
		int start = pq.top().first.second;
		int end = pq.top().first.first - 1;
		int num = pq.top().second;
		pq.pop();
		int cnt = 0;
		FUP(i, start, end)
		{
			cnt = max(cnt, box[i]);
		}
		FUP(i, start, end)
		{
			num = min(num, C - cnt);
		}
		ans += num;
		FUP(i, start, end)
		{
			box[i] += num;
		}
	}
	COUT(ans);

	return 0;
}