[Baekjoon] 1931번: 회의실 배정

 

 

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

1931번: 회의실 배정

 

---

 

문제 해결 과정

착안

문제를 처음 접하고 어떻게 해결할 지 막연해서 꽤 오래 고민을 했다. 최대한 많은 회의에 대해 회의실을 배정하려면 어떻게 해야할지 열심히 생각해보다가, 아래와 같은 조건들이 문제 해결의 핵심이라고 생각을 했다.

 

처음 생각한 조건

• 회의 시간이 짧은 회의들을 가능한 한 많이 배정한다.
• 회의실이 비는 시간을 최소로 한다(단, 회의실 배정 가능한 시간에 대해 별도의 제약이 없음에 유의)

 

위의 조건을 만족하면서 회의를 순차적으로 배정하다보면 결과적으로 최대한 많은 회의에 대해 회의실을 배정할 수 있을 것이라고 생각을 해서, 탐욕(greedy) 알고리즘을 적용해보고자 하였다. 위의 두 조건을 동시에 만족하면서 앞쪽 시간대의 회의부터 회의실을 배정하는 부분 최적해를 생각해보면 다음과 같다.

* 이 부분은 문제로 주어질 수 있는 여러 케이스를 가정해보고, 시행착오를 통해 발견하였다.

  예를 들어, 회의 시간 5개가 (2 4), (2 3), (3 4), (3 3), (3 3)으로 주어지는 경우를 놓고 정렬 방법을 고민했다.

 

수정한 조건

• 종료 시간이 빠른 회의부터 배정한다(먼저 배정된 회의가 끝나야 다음 회의를 또 진행할 수 있기 때문)

 

위와 같은 방법으로 부분 최적해를 구해나가는 과정을 통해 문제를 해결해보고, 해결되지 않으면 다른 알고리즘을 적용해보고자 하였다. 이때, 특히 시작 시간과 종료 시간이 같은 회의가 존재한다는 점에 유의하였다.

* 이 문제에서 회의 시간에 대한 시작점이 확실하게 0으로 존재하지만 마지막 시간이 언제인지는 입력된 값들을 살펴봐야 알 수 있기 때문에, 자연스럽게 앞에서부터 회의를 채워넣는 식으로 생각을 하여 위와 같이 종료 시간을 우선 기준으로 정렬하고자 했다. 뒤에서부터 회의를 배정하는 경우(시작 시간을 우선 기준으로 정렬)도 가능할 수는 있을 것 같은데, 만약 그렇다면 이때는 회의 시작 시간이 같은 경우에 더 늦게 종료하는 회의부터 배정하도록 기준을 바꾸어야 할 것이다.

 

구현

탐욕 알고리즘을 구현하기 위해, 시간대 순서에 따라 단계별로 부분 최적해를 구해야하므로 입력으로 주어지는 회의 시간(시작 및 종료 시간)을 정렬하는 것이 필요하다. 따라서 입력받는 회의 시간에 대한 구조체를 만들고, 이를 우선 배열에 저장한 다음 <algorithm> 헤더의 std::sort() 함수를 사용해 정렬하였다. 정렬 기준은 착안한 내용과 같이 이항 조건(binary predicate)을 만들어 전달하였다.

 

회의 시간 정보를 요소로 가지는 배열을 정렬한 뒤, 처음 요소부터 순차적으로 회의실을 배정하면서 배정된 회의가 끝난 뒤에 새로운 회의를 배정할 수 있도록 구현하기 위해 별도의 변수를 선언하여 조건문을 이용해 제어하였다.

 

코드를 구현해본 다음, 시작 시간과 종료 시간이 같은 회의가 존재할 때도 제대로 작동하는지 테스트를 해보았는데 잘 작동함을 확인하여 그대로 코드를 제출했다.

 

[스포 주의] 아래 '더보기'를 누르면 코드가 나오니 주의하세요~

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

using namespace std;

struct Meeting
{
	int Start;
	int End;
};

vector<Meeting> Meetings;

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N;
	cin >> N;

	vector<Meeting> Meetings(N);
	for (int i = 0; i < N; i++)
	{
		int t1, t2;
		cin >> t1 >> t2;
		Meetings[i] = Meeting{ t1, t2 };
	}

	sort(Meetings.begin(), Meetings.end(),
		 [](const Meeting& a, const Meeting& b)
		 {
			 if (a.End == b.End)
				 return a.Start < b.Start;

			 return a.End < b.End;
		 });

	int Start = 0, Count = 0;
	for (Meeting meeting : Meetings)
		if (meeting.Start >= Start)
		{
			Count++;
			Start = meeting.End;
		}

	cout << Count << "\n";
	return 0;
}

 

실행 결과