[C++ 백준 1931번] 회의실 배정 (그리디)

문제

문제 분석

문제를 읽고 아이디어가 필요한 문제이다.

N이 10만이므로 O(n^2)을 넘기면 안되고 다소 아이디어가 필요할 수 있다는걸 생각해볼 수 있었다.

 

최소 회의수를 구하기 위해 정렬을 해야될 것 같은 느낌이 들었고 정렬과 연결되어 하나의 최적해가 문제를 푸는데 일반화될 수 있다면 그리디 알고리즘에 해당될 수 있다는 것을 눈치챌 수 있었다.

 

문제를 풀기 위한 아이디어는 먼저 시작 시간을 내림차순으로 정렬하고, 해당 미팅의 종료 시간 <= 그 이전 미팅의 시작 시간이면 된다는 아이디어를 이용했다.

정답 코드

아이디어만 있으면 아이디어대로 구현만 하면 되는 문제이다.

- 정렬, pair 자료구조에 대한 이해만 있으면 된다.

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

using namespace std;
vector<pair<int, int>> time_table;

bool cmp(const pair<int, int> p1, const pair<int, int> p2) {
	if (p1.first != p2.first) return p1.first > p2.first; // 1순위 :시작 시간을 기준으로 내림차순
	return p1.second > p2.second; // 2순위 : 시작 시간이 같은 경우 끝 시간을 기준으로 내림차순 
}

int main(void) {
	ios_base::sync_with_stdio(false); cin.tie(nullptr);
	int n;
	cin >> n;
	for (int i = 0; i < n; i++) {
		int start, end;
		cin >> start >> end;
		time_table.push_back(make_pair(start, end));
	}
	sort(time_table.begin(), time_table.end(), cmp);

	int ok_metting_time = 0; // 회의 가능 시간 
	int ans = 0; // 총 회의 횟수

	for (int i = 0; i < time_table.size(); i++) {
		// 처음 시작에는 가장 뒷 시간
		if (i == 0) {
			ok_metting_time = time_table[i].first;
			ans++;
			continue;
		}
		
		// 해당 미팅의 종료 시간 <= ok_metting_time -> 미팅 진행
		if (time_table[i].second <= ok_metting_time) {
			ans++;
			ok_metting_time = time_table[i].first;
		}
		// 해당 미팅의 종료 시간 > ok_metting_time -> 미팅 미진행
	}

	cout << ans;

	return 0;
}

 

교훈점

뭔가를 정렬해야 되는 경우 그리디 알고리즘을 의심해보자.

N이 큰 경우 아이디어가 필요한 그리디 문제가 될 수 있다는 것을 의심해보자.