[백준 28305번] 세미나 배정 C++ 풀이

UCPC 예선에 고전했던 문제로 결국 풀지 못하고 대회가 끝나고 업솔빙하였다.

1. 문제

 

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

28305번: 세미나 배정

문제를 설명하면 

$ N $ (세미나의 개수) 와 $ T $ (세미나기간) 가 주어지고 

$ a_1, a_2,,, a_N $ 가 주어 지는데 각각 $ i $번째 세마나가 반드시 진행되야하는 시간이다.

이떄 세미나가 가장 많은 날의 세미나 수의 최솟값을 구해야한다.

예를 들어 위와 같이 input이 주어졌다면 총 2개의 세미나 수가 동시에 진행된다.

첫번째 세미나가 4~6일에 진행되고,

두번째 세미나가 6~8일에 진행되고,

세번째 세미나가 1~3일에 진행되고,

네번째 세미나가 3~5일에 진행되고,

다섯번째 세미나가 7~9일에 진행될때,

3~8일에 2개의 세미나가 동시에 진행되고 2개보다 작은 세미나 동시에 진행되면서 세미나가 진행되는 경우가 존재하지 않아 2개가 답이다.

2. 접근

옳은접근 (Greedy + Bst)

시간제한은 2초, $ 1 \leq  N \leq  200000 $ 으로 최대 $ Nlog(N) $ 까지 가능하다.

우리가 확실하게 검증할수 있는 방법을 생각해보자.

브루트포스를 사용한다고 생각하면 $ 1 \leq  i \leq  200000 $ 의 모든 $i$에 대해서 각각 에 대해 동시에 진행되는 세미나가 최대 $i$일때의 input의 세미나를 배치할수 있는지 구할수있다. ($i$길이 배열에 각각 세미나가 끝나는 시간을 넣어 계속 갱신하는 방식으로 구현할 수 있다)

단조증가하는 형태이므로 이분탐색을 사용하여 만족하는 $i$의 최솟값을 구할 수 있다.

 

 

틀린접근 (Greedy + Prioirty queue)

문제를 읽자마자 떠오른 것은 스위핑을 이용한 방법이였다.

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

19598번: 최소 회의실 개수

위 문제와 상당히 유사한 형태라고 판단하여 우선순위 큐를 이용하여 구현하고자 했다.

그렇게 된다면 우선순위 큐에 어떤 값을 기준으로 sorting 할건지 정해야 하는데, $ a_i $ 값을 기준으로 sorting 하고자 하였다.

직관을 사용하면 모든 세미나의 소요시간 $ K $으로 같으므로 $ a_i $ 가$ a_j $ 작다면 결국 $ i $ 번째 회의가 $ j $ 번째 회의 보다 같거나 더빨리 시작되는 것이 최적의 방법임을 알 수 있다.

먼저 $ a_i $들을 오름차순으로 sorting 하고 우선순위 큐에 세미나가 끝난 시간을 넣어 최솟값인 pq.top()을 가져와 새로운 세미나를 해당 세미나실에 이어서 진행할수있으면 세미나실이 다시 사용할 수 있는 을 갱신하여 우선순위 큐에 push하였고, 그렇지 않으면 새로운 세미나실을 배정하여 push하는 방식으로 구현하였다.

그런데 위와같은 그리디전략은 옳지 못하는데 $ a_i $ 중 같은 값이 있을때 최적의 조합을 찾을 수 없다.

따라서 위 방법을 사용하면 wa이다.(증명을 꼼꼼히 합시다ㅠㅜ)

3. 구현

#include<iostream>
#include<algorithm>
using namespace std;
int arr[200001] = { 0 };
int N, T;
int dp[200001] = { 0 };
bool cal(int num) {
	for (int i = 0; i < N; i++) {
		dp[i] = arr[i];
	}
	if (num == 0)
		return false;
	for (int i = 0; i < N; i++) {
		if (i < num) {
			if (dp[i] >= T) {
				dp[i] = arr[i] + 1;
			}
			else {
				dp[i] = T + 1;
			}
		}
		else {
			if (dp[i - num] > arr[i])
				return false;
			if (dp[i - num] + T <= arr[i] + 1) {
				dp[i] = arr[i] + 1;
			}
			else
				dp[i] = dp[i - num] + T;
		}
	}
	return true;
}
int bst() {
	int head = 1;
	int tail = 200000;
	int mid = (head + tail) / 2;
	while (head < tail) {
		//cout << "head: " << head << " mid: " << mid << " tail: " << tail << endl;
		//cout << cal(mid) << endl;
		if (cal(mid)) {
			tail = mid - 1;
		}
		else {
			head = mid + 1;
		}
		mid = (head + tail) / 2;
	}
	//cout << "mide: " << mid << endl;
	if (!cal(mid))
		mid++;
	return mid;
}
int main() {
	cin.tie(NULL);
	ios::sync_with_stdio(false);
	cin >> N >> T;
	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}
	sort(arr, arr + N);
	cout << bst();
	return 0;
}

이분탐색할때 예외를 처리하지 않아 몇번더 틀렸다. 이분탐색을 구현할때 항상 실수를 하는데 연습을 많이 해야겠다.