BOJ 1931: 회의실 배정

백윤재·2021년 8월 20일

boj cpp greedy ps

BOJ

목록 보기

5/28

✔ 문제 링크

BOJ 1931: 회의실 배정

✔ 문제해결전략

Greedy

✔ 해결과정

✔ Why Greedy?

완전탐색: O(2^n)이라 불가능

DP: d[i] = i번째 회의를 끝으로 할 때 진행한 최대 회의 수(끝나는 순으로 정렬 후) => O(n^2)이라 불가능

So, 탐색 범위를 줄여보자

회의들을 끝나는 시간 순으로 정렬하고 각 상황에서 가장 먼저 끝나는 회의를 택하자

이러한 선택이 정당하다는 것은 귀류법으로 보일 수 있다

✔ Proof

target: 현재 시간이 time일 때 time 이후의 모든 회의 중에서 가장 먼저 끝나는 회의를 택하는 것이 최적해이다.

만약 target이 거짓이라 가정하자. 그러면 time 이후의 모든 회의 중에서 가장 먼저 끝나지 않는 회의를 택하는 경우 중에서 최적해가 있다. 그런데 그 회의 대신 가장 먼저 끝나는 회의를 택해도 최소한 그 회의를 택했을 때 만큼의 회의는 진행할 수 있다. 즉, 모순.

So, target은 참

✔ Code

#include <bits/stdc++.h>
using namespace std;


int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n, cnt = 0;
	vector<pair<int, int> > m;
	
	cin >> n;
	m.resize(n);
	
	for(int i=0;i<n;i++) {
		// first: end, second: start
		cin >> m[i].second >> m[i].first;
	}
	sort(m.begin(), m.end());
	
	int time = 0;
	
	for(int i=0;i<n;i++) {
		if(m[i].second < time) continue;
		time = m[i].first;
		cnt++;
	}
	
	cout << cnt;
}

✔ Check Point

회의가 끝나는 시간순으로 정렬할 때 편하게 하기 위해 pair의 second에 시작 시간을, first에 끝나는 시간을 입력받았다. sort 함수에 정렬 기준 함수를 인자로 주는 대신 이렇게 하는 것이 훨씬 간단한 것 같다. 가끔 이런 식으로 first, second에 들어가는 값의 순서에 변화를 주는 것이 좋은 경우도 있다는 것 기억하자.