#1931번 회의실배정 (C++)

링크 : www.acmicpc.net/problem/1931

1931번: 회의실배정

처음에는 순서대로 값을 받고 직접 두 번째 값을 나열하기 위한 비교 함수를 선언했다. 

그런다음 DFS방식으로 문제에 접근했고, 테스트 케이스를 통과하였다.

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

using namespace std;

int n = 0, temp = 0, ans = 0;
vector<pair<int,int>> v;

bool compare(pair<int, int>& a, pair<int, int>& b) {
	if (a.second == b.second) return a.second < b.second;
	else return a.second < b.second;
}

void dfs(int t, int total) {
	temp = v[t].second;
	for (int i = t; i < n; i++) {
		if (v[i].first >= temp) {
			dfs(i, total + 1);
		}
	}
	if (ans < total) ans = total;
}

int main(void) {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	int a = 0, b = 0;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		v.push_back(make_pair(a, b));
	}
	sort(v.begin(), v.end(), compare);

	for (int i = 0; i < n; i++) {
		dfs(i,1);
	}
	cout << ans << "\n";
	return 0;
}

하지만 DFS가 정답은 아니였는지, 시간초과가 나와버렸다. 

 

고민끝에 다음과 같은 식을 세웠다.

 

1. 값을 받을때 뒤집어서 받는다.
   즉, 저장되는 값은 (회의 종료 시간, 회의 시작시간)이다. 
2. 배열을 오름차순으로 정렬한다.
   이렇게해서 가장 빨리 종료되는 회의가 먼저 저장되고, 정답값은 1부터 시작하게 된다. 
   (*가장 많은 회의를 진행하는게 목표이므로, 회의 시작이 아닌 종료를 기점으로 판단해야한다.)
3. 회의 종료시간과 그 다음 회의의 시작시간을 순차적으로 비교한다. 
   종료시간과 그 다음회의의 시작시간이 같거나 후자가 더 클 경우, 다음 회의는 진행이 가능한 회의이다. 

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

using namespace std;

int main() {
	ios::sync_with_stdio(NULL);
	cin.tie(NULL);

	int n = 0, a = 0, b = 0, ans = 1;
	vector<pair<int, int>> v;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a >> b;
		v.push_back(make_pair(b, a));
	}
	sort(v.begin(), v.end());
	a = v[0].first;
	for (int i = 1; i < n; i++) {
		if (a <= v[i].second) {
			ans++;
			a = v[i].first;
		}
	}
	cout << ans << "\n";
}