회의실 배정 1931

문제 해설 및 주의사항

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다.

 

각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자.

 

단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

 

---

 

풀이

1. 브루트 포스?

- N 이 100,000 최대라는 것만 봐도 일단 브루트 포스에 거부감이 느껴진다. 2^100,000 불가능하다.

 

2. 브루트 포스가 아님을 파악하고 나니, 어떤 문제 유형인지 모르겠다.

- 그리디 알고리즘?

 

3. 그리디 알고리즘

- 선택하는 순간에 가장 최적인 방법이 무엇인지 생각해보자.

 

a. 가장 일찍 시작하는 회의를 배정한다.

b. 가장 짧은 회의를 먼저 배정한다.

c. 가장 일찍 끝나는 회의를 배정한다.

 

a, b 는 반례를 쉽게 생각해낼 수 있지만, c 는 없다. 일단, c 라고 생각하고 해보자.

증명은 어떻게 할까?

문제의 정답 이 있고 그리디로 구한 정답 이 있다고 생각해보자.

그리디로 구한 답이 항상 문제의 정답이 되는가? 라는 것을 증명하자.

현재 상태이다

현재, 그리디로 구한 답과 문제의 정답은 다르다. (갯수는 같지만) 이때, 문제의 정답을 그리디로 구한 정답으로 바꾸어보자.

만약 바꾸었을 때, 회의를 더 선택할 수 있게 된다면, 그리디로 구한 정답 = 문제의 정답이라는 가정이 모순이 되기 때문에 틀리는 것이다. 하지만, 현재는 답이 일정하게 유지되기 때문에 맞다.

위와 똑같이, 3번 정답도 그리디로 바꾸어 보는 것이다.

마찬가지로, 3번을 옮겼는데, 원래는 선택할 수 없었던 것이 선택 가능하게 되어 답이 달라지면 그리디 알고리즘이 틀린 것이지만, 바뀌지 않아서 맞다.

※ 그리디 알고리즘이라는 증명은 문제마다 다르다.

 

---

풀이코드

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <queue>
#include <tuple>
using namespace std;
// 회의실 배정 1931

struct Meeting{
	int begin, end;
};

// sort 를 위한 함수
bool cmp(const Meeting &u, const Meeting &v){
	// 끝 시간이 같으면, 시작 시간 기준으로 정렬
	if(u.end == v.end){
		return u.begin < v.begin;
	} else{ 
		// 끝 시간을 기준으로 정렬
		return u.end < v.end;
	}
}

int main(){
	int n;
	scanf("%d", &n);
	vector<Meeting> meetings(n);
	for(int i = 0; i < n; i++){
		scanf("%d %d", &meetings[i].begin, &meetings[i].end );
	}
	sort(meetings.begin(), meetings.end(), cmp);
	
	// 회의가 끝난 시간
	int now = 0;
	int ans = 0;
	
	for(int i =0 ; i < meetings.size(); i++){
		// 현재 끝난 시간 보다, 시작 시간이 더 크면
		if(now <= meetings[i].begin){
			now = meetings[i].end;
			ans += 1;
		}
	}
	
	printf("%d\n",ans);
	
}

 

---

퇴고

1. 그리디 알고리즘을 판별하는 방법

- 사실상, 느낌이다. 엄청난,  그리디 판별법 이런 것을 기대하기 보다는 많은 유형을 풀어보면서 감을 잡자.

 

2. cmp 함수의 작성을 잘 배워가자.