[C++] Softeer Lv.3 강의실 배정

출처

https://softeer.ai/practice/6291

 

 

 

 

 

문제 

김교수는 강의실 1개에 최대한 많은 강의를 배정하려고 한다. 배정된 강의는 서로 겹치지 않아야 하며 수업시간의 길이와 상관없이 최대한 강의를 많이 배정하라. 단, 두 강의의 시작시간과 종료시간은 겹쳐도 된다.

 

 

제약조건

1 ≤ N ≤ 106 인 정수
1 ≤ Si ＜ Fi ≤ 109

 

 

 

입력

첫 번째 줄에 강의 개수 N이 주어진다. i + 1 (1 ≤ i ≤ N)번째 줄에는 i번째 강의의 시작 시간 Si와 종료 시간 Fi가 주어진다.

 

 

 

출력

첫 번째 줄에 최대 강의 수를 출력하라.

 

 

 

풀이

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

int main() {
	int N;
	scanf("%d", &N);
	vector<pair<int, int>> lecture(N);
	for (int i = 0; i < N; i++)	{
		scanf("%d %d", &lecture[i].second, &lecture[i].first);
	}
	// 빨리 종료하는 것 부터 시작
	sort(lecture.begin(), lecture.end());
	// 끝나는 지점 중, 가장 앞부분부터 시작
	int current = lecture[0].first;
	int cnt = 1;
	// 탐색 시작
	for (int i = 1; i < N; i++) {
		// 이미 채택된 강의의 종료 시간이 탐색 중인 강의의 시작 시간보다 앞일 때, 해당 강의 채택 
		if (current <= lecture[i].second) {
			current = lecture[i].first;
			cnt++;
		}
	}
	printf("%d", cnt);

}

 

해당 문제는 Greedy Algorithm, 현재 순간에서 가장 최적인 답을 고르면 해결되는 문제이다.

이는 두가지 속성을 만족했을 때 적용할 수 있다.

• 탐욕 선택 속성(greedy choice property):  각 단계에서 최적이라고 생각되는 선택을 했을 때, 그 선택이 전체 문제에 대한 최적해의 일부가 되는 성질
• 최적 부분 구조(optimal substructure) 특성: 문제의 최적해가 그 부분 문제들의 최적해로 구성될 수 있는 성질

최적의 답을 찾는 것에만 집중하다보니, 간단한 알고리즘을 간과했다. 

그리디 알고리즘은 최적의 답을 보장하지 않는다는 것을 기억해두자~!