[그리디, 난이도 중] 백준 1931번 회의실배정

첫 그리디 문제풀이 포스팅이다.

다이나믹(동적계획법) 알고리즘과 그리디(탐욕) 알고리즘의 차이는 이 포스팅에서 다루었다.

https://kimcoder.tistory.com/32

[동적계획법, 난이도 중] 백준 1463번 1로 만들기

여러 회의들의 시작 시간, 끝 시간을 알아내어 최대한 많은 회의를 하는 경우를 계산해야 하는 문제이다.

회의가 끝나는 시각이 이른 순으로 정렬하고, 끝나는 시각이 같다면 시작 시각이 늦은 순으로 추가 정렬을 해준다.

 

이 문제의 정답률이 28%인 이유는 아마 예제 입력에서 많은 혼동이 왔던게 아닌가 싶다.

예제 입력1은 이미 이 정렬이 완료 되어있다.

즉 많은 분들이 뒤죽박죽 섞여 있는 데이터에 대해서는 처리를 할 생각을 미처 못했던 모양이다.

 

정렬을 끝내고 이 과정을 수행해주면 문제를 해결할 수 있다.

첫 기준점 cur은 0이다. 이 기준점의 의미는 아래 과정에서 이해할 수 있을 것이다.

 

1. 가장 끝나는 시각이 이른 회의를 택한다. (위 그림에서 <1~4>)

2. 그 회의의 끝나는 시각에 기준점(cur) 을 걸어둔다. (위 그림에서 cur->4) 

3. 계속 뒤로 정렬된 회의들을 탐색하며 시작 시각이 cur이상인 회의를 고른다.

4. 모든 회의를 탐색 할 때 까지 2~3 과정을 반복한다.

 

여기서 한가지 주의 사항이 있다.

이 문제에서 회의가 끝난다는 의미가 헷갈릴 수 있는데

회의가 시각 4때 끝났어도 시각 4때 다른 회의를 시작할 수 있다.

즉 if (v[curindex].first >= cur) 에서 >가 아닌 >= 를 사용했다.

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

using namespace std;
bool cmp(pair<long long, long long> a, pair<long long, long long> b) {
	if (a.second == b.second) return a.first < b.first;
	else return a.second < b.second;
}
int main() {
	int n;
	cin >> n;
	vector<pair<long long, long long> > v;
	for (int i = 1; i < n + 1; i++) {
		long long start, finish;
		cin >> start >> finish;
		v.push_back(pair<long long, long long>(make_pair(start, finish)));
	}
	sort(v.begin(), v.end(), cmp);

	long long cur = 0;
	int curindex = 0;
	int count = 0;
	while (curindex<n) {
		if (v[curindex].first >= cur) {
			cur = v[curindex].second;
			curindex++;
			count++;
		}
		else curindex++;
	}
	cout << count;
}