[백준] 1931 회의실 배정 - C++

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

---

제한된 시간 안에 가장 많은 회의를 진행해야 한다.

아주 탐욕적이고 직관적으로 생각했을 때, 이 문제를 풀 로직으로 두개가 생각났다.

1. 회의시간이 가장 짧은 회의를 선택

2. 끝나는 시간이 가장 빠른 회의를 선택

회의를 위의 로직대로 오름차순 정렬해 하나씩 선택 할 것이다.

 

1번 로직은 A(1~2), B(3~50), C(50~51)의 세 회의가 주어졌을 때,

회의시간이 짧은 A-C-B 순으로 선택하게 된다.

이때 C를 고른 시점에서 B는 고를 수 없기 때문에 (B는 3에 시작하는 회의라서) 얻는 답은 2가 된다.

하지만 우린 이게 답이 아니란걸 안다. 딱봐도 A-B-C 순이므로 답은 3이다.

따라서 1번 로직은 탐욕적이지만 이 문제에는 적합하지 않다.

 

반대로 2번 로직의 경우에는 위와 같이 A(1~2), B(3~50), C(50~51)의 세 회의가 주어졌을 때,

끝나는 시간이 빠른 A-B-C 순으로 선택한다. 이렇게 하면 정답인 3을 얻을 수 있다.

2번 로직이 문제를 풀기에 적합한 것 같다.

 

바로 풀어보도록 하자. 그리디는 로직만 잘 세워두면 구현은 금방 한다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool compare(pair<int, int> a, pair<int, int> b) {
	if (a.second == b.second) {
		return a.first < b.first; // <1>
	}
	else {
		return a.second < b.second;
	}
}
int main() {
	int n;
	cin >> n;
	vector<pair<int, int>> v;
	for (int i = 0; i < n; i++) {
		pair<int, int> buf;
		cin >> buf.first >> buf.second;
		v.push_back(buf);
	}
	sort(v.begin(), v.end(), compare);
	int cnt = 0;
	int ended_time = 0;
	for (int i = 0; i < n; i++) { // <2>
		if (ended_time <= v[i].first) {
			ended_time = v[i].second;
			cnt++;
		}
	}
	cout << cnt;
	return 0;
}

시작하는 시간을 first, 끝나는 시간을 second로 받는 pair타입의 vector를 사용한다.

입력을 받은 후 이를 정렬하는데, compare 함수를 보면 알 수 있듯이 끝나는 시간이 빠른 순으로 정렬한다.

 

<1> : 끝나는 시간이 같은 경우엔 시작 시간이 빠른 순으로 정렬한다. 이 부분에서 의문이 들 수 있는데,

예를 들어 A(1~10), B(10~10)이라는 두 회의가 있다고 가정하자.

문제 조건에서 시작하는 시간과 끝나는 시간이 같을 수 있다고 했기 때문에 가능한 예시이다.

이 두 회의 중 시작시간이 빠른 A를 선택해야 A가 끝난 뒤 B를 진행하지 않겠는가..

이런 이유에서 시작 시간이 빠른 순으로 정렬한다.

 

<2> : 이  for문은 정렬된 vector의 원소를 하나씩 선택하고, 선택된 회의가 끝난 시간인 ended_time을 저장한다.

이를 통해서 현재 선택한 회의가 끝나기도 전에 시작하는 회의는 거른다.

---

그리디 문제를 풀면 여러 관점에서 문제를 바라보는 능력이 느는 것 같다.

많이 풀어보면서 연습하도록 하자.

---