[백준] 11000번: 강의실 배정 C++ 풀이

 

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

 

 

이 문제는 Greedy 알고리즘을 이용한 문제입니다.

우선순위 큐를 이용하면 쉽게 풀어낼 수 있습니다.

그러나, 이 문제를 해결할 때 아이디어를 떠올리기 쉽지 않아서 관련 정보를 찾아봤는데, 생각보다 간단한 해결책이 존재했습니다.

 

이 알고리즘은 단순히 하나의 강의실에서 종료시간이 빠른 강의 뒤에 최대한 시작시간이 빠른 강의가 오도록 하면 최소값이 나오는 원리였습니다.

 

즉,  남은 강의 중 최대한 빨리 시작하는 강의 시작 시간이 t = 10 이라고 가정할 때,

만약 이미 강의실에서 진행 중인 강의들 중 가장 강의 종료 시간이 빠른 시각이 t = 12 (즉, 제일 빨리 시작 예정인 강의보다 크면) 새로운 강의실을 만들어주면 됩니다.

 

말로 하려니 어려우니, 아래 코드를 보며 이해하면 좋습니다.

 

#include <iostream>
#include <algorithm>
#include <queue>
#include <vector>

using namespace std;

struct lecture
{
	int start;
	int end;

	bool operator<(const lecture& other) const {
		if (start == other.start)
			return end > other.end;
		return start > other.start;
	}
};

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL); cout.tie(NULL);
	int N;
	cin >> N;
	int b, c;
	priority_queue<lecture> pq;
	priority_queue<int> v;
	for (int i = 0; i < N; i++)
	{
		cin >> b >> c;
		pq.push({ b,c });
	}

	v.push(- pq.top().end);
	pq.pop();
	while (!pq.empty())
	{
		int start = pq.top().start;
		int end = pq.top().end;
		
		// 이미 있는 강의실 사용 가능한 경우
		if (-v.top() <= start)
		{
			v.pop();
		}
		v.push(-end);
		pq.pop();
	}
	cout << v.size();
}

 

 

lecture 라는 자료구조를 하나 만들어서 우선순위 큐로 만들어줍니다.

(지금 생각하니 vector로 sort 해도 가능한 알고리즘인 것 같습니다.)

 

pq: 강의 목록(시작 시각, 종료 시각 기준으로 오름차순으로 정렬)

v: 강의실 목록(종료 시각으로만 저장)

 

v 에서 강의실 목록만 저장하면 되는 이유는 시작 시각에 관계 없이 종료 시각 후만 계산하면 되기 때문입니다.