Boj 19623) 회의실 배정 4

문제

백준 19623

설명

Weighted Activity Selection 문제로 위키에 있을 정도로 Well Known 문제이다.

처음 접근한 방법은 다음과 같다. dp[i] 를 i 번째 시각까지의 가능한 최대인원으로 두고 다음과 같은 점화식을 세운다.

dp[종료시각] = max(dp[종료시각]], dp[시작시각] + 최대인원)

dp[i] 가 i 이전까지의 최대인원임을 보장하기 위해서 2가지를 만족시킨다. 1. 종료시각이 빠른 미팅부터 점화식을 돌린다. 2. 단순 대입은 범위 내의 최댓값을 보장하지 않으므로 세그트리로 로그단위 안에 업데이트 한다. 또한 시간범위가 넓으므로 좌표압축을 수행한다.

위의 전략을 통해 나는 맨 처음 문제를 해결했지만, 점화식을 조금만 수정하면 간단히 풀리는 문제였다.

dp[meet[i].종료시각] = max(dp[meets[i-1].종료시각], dp[meets[i].시작시각 이하의 가장 큰 종료시각] + meets[i].최대인원)

Greedy Strategy 를 통해 Activity Selection 을 풀 때 처럼 종료시각을 기준으로 회의를 정렬한다. 그리고 위 점화식을 수행하면 dp[i] 는 i 번째 종료시각까지의 가능한 최대인원이 된다. 여기에 모든 회의의 종료시각이 다르므로 그냥 회의의 인덱스를 사용하면 좌표압축을 할 필요도 없다. 어떤 시각 이상의 가장 작은 종료시각은 이분탐색으로 구하면 빠르게 구할 수 있다.

시간 복잡도

O(\(\mathrm{N}\log{\mathrm{N}}\))

코드

struct MEET { unsigned int s, e; int p; } meets[100001];
int n, dp[100001]; // th번째의 Meeting 중에 최대인원

int main()
{
	cin >> n;
	for (int i = 0; i < n; ++i)
		cin >> meets[i].s >> meets[i].e >> meets[i].p;
	sort(meets, meets + n, [](MEET& a, MEET& b) { return a.e != b.e ? a.e < b.e : a.s < b.s; });

	dp[0] = meets[0].p;
	for (int i = 1; i < n; i++)
	{
		int t = lower_bound(meets, meets + i, meets[i], 
                            [](const MEET&a, const MEET& b) { return a.e < b.s; }) - meets;
		// 시간이 같은 경우는 없으므로 -1 을 하면 ~보다 작은 것중에 가장 큰 것이 된다.
		dp[i] = max(dp[i - 1], (t > 0 ? dp[t-1] : 0) + meets[i].p);
	}
	cout << dp[n-1];
}