(백준/C++) 1931_회의실 배정
탐욕 알고리즘(Greedy Algorithm)이란, 매 순간 최적이라고 생각되는 방법을 선택하는 방식으로 문제를 해결하는 알고리즘입니다.
즉, 다른 경우의 수가 없이 현 문제에서 가장 좋아 보이는 것을 선택해 나가다보면 문제가 풀리는 알고리즘 입니다.
1931번: 회의실 배정 (acmicpc.net) 문제는 어떻게 탐욕 알고리즘으로 풀 수 있는거지? 하고 생각하실 수도 있는데, 다음과 같은 조건으로 탐욕 알고리즘을 적용할 수 있습니다.
시작 시간과 끝나는 시간은 같은 자연수 또는 0이다
모든 시간은 0 이상의 자연수입니다. 즉, 23시 ~ 02시와 같이 시간이 섞이는 경우가 없습니다.
즉, 0시부터 차근차근 회의를 배정할 수 있습니다.
접근법
생각해보면 탐욕 알고리즘은 매 순간 최적의 선택을 하기 위해 사용되므로, 특정 기준에 따라 데이터를 정렬하면, 그 기준에 따라 최적의 선택을 할 수 있게 됩니다.
예를 들어, 동전 문제의 경우 동전의 가치를 내림차순으로 정렬하면, 가장 큰 가치의 동전부터 사용할 수 있습니다.
회의실 배정 문제도 특정 기준에 따라 정렬하는 것으로 탐욕 알고리즘을 적용할 수 있게 됩니다.
1) 회의가 빨리 끝날수록 더 많은 회의를 배정할 수 있다.
위에서 언급했듯이 이 문제는 모든 시간이 0 이상의 자연수입니다.
따라서, 0시부터 차근차근 회의를 배정하면 되는데,
이때, 회의가 빨리 끝나면 다음 회의를 배정할 수 있다는 단순한 논리를 적용할 수 있습니다.
즉, 회의 종료 시간이 빠른 순으로 정렬하면 가장 먼저 끝나는 회의부터 차례대로 배정할 수 있습니다.
2) 회의가 종료되자마자 다음 회의를 배정할 수 있다.
1) 에서 회의가 종료되는 순서대로 정렬을 했으니 회의가 종료되는 시간을 가지고 바로 다음에 시작할 수 있는 회의를 찾을 수 있습니다.
어쩌면 현재 선택된 회의 바로 다음 회의가 될 수도 있습니다.
예를 들어 다음과 같은 경우가 생길 수 있습니다.
1
2
3
4
1 4
4 5
4 7
4 8
회의가 종료되는 시간 순으로 정렬하면 위와 같이 바로 다음 요소가 바로 다음 회의가 될 수 있습니다. 혹은 중간에 2 5 와 같은 시간이 추가되어 있더라도 종료시간인 4 이후의 시작 시간을 바로 찾아 선택할 수 있습니다.
3) 회의는 바로 시작해서 바로 끝날 수 있다.
회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.
이 조건을 보면 회의의 시작 시간과 종료 시간이 같은 경우가 있습니다.
이 경우도 생각해서 배정해야 하는데, 그러기 위해서는 회의 종료 시간이 같은 경우 시작 시간이 빠른 순으로 정렬해야 합니다.
만약, 종료시간만으로 정렬해서 틀렸다면 위 조건을 생략한 경우입니다.
예를 들어 종료시간만으로 정렬하면 다음과 같은 경우가 발생할 수 있습니다.
1
2
3
4
5
1 2
4 4
3 4
2 4
4 7
위와 같은 경우 2 4 나 3 4 의 회의가 생략될 수 있습니다. (1 2 - 4 4 - 4 7)
만약 4 4 가 뒤에 있었다면 2 4 가 선택되던 3 4 가 선택되던 하나 더 배정 될 수 있었을 것입니다.
이 경우, 시작시간으로 정렬하는 경우에는 이 부분을 해결할 수 있습니다.
1
2
3
4
5
1 2
2 4
3 4
4 4
4 7
위와 같이 정렬된다면 1 2 - 2 4 - 4 4 - 4 7 로 올바르게 배정할 수 있습니다.
풀이
pair로 시작 시간과 종료 시간을 한꺼번에 저장하고, 종료 시간이 같다면 시작 시간이 빠른 순으로 정렬해주었습니다.
그리고 순서대로 탐색하면서 종료 시간 이후의 회의를 선택해 나가면 탐욕 알고리즘으로 문제를 풀 수 있습니다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool compare(pair<int, int>& a, pair<int, int>& b)
{
if (a.second == b.second)
return a.first < b.first;
return a.second < b.second;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
int N, count = 0;
cin >> N;
vector<pair<int, int>> times(N);
for (int i = 0; i < N; i++)
cin >> times[i].first >> times[i].second;
sort(times.begin(), times.end(), compare);
int endTime = 0;
for (pair<int, int>& time : times)
{
if (time.first >= endTime)
{
endTime = time.second;
count++;
}
}
cout << count;
}