https://www.acmicpc.net/problem/1931
문제
> 한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다.
> 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자.
> 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다.
> 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.접근
빨리 끝날 수 있는 회의 부터 쳐내야 많은 수의 회의를 할 수 있기 때문에 끝나는 시간으로 정렬을 한 뒤 회의를 배치한다.
문제해결
> 회의의 수, 회의의 시작과 끝시간을 입력받아 벡터에 저장한다.
그리고 정렬을 하는데 회의의 끝나는 시간을 기준으로 빠른순서대로 정렬한다.
만약 끝나는 시간이 같다면 시작시간이 빠른순서대로 정렬한다.
> 정렬한 뒤 첫 인덱스의 끝나는 시간이 가장 빠른시간 이므로 이를 복사해온다. 다음으로 이 시간보다 크거나 같은 시간을 시작 시간으로 갖는 회의의 끝시간으로 다시 갱신시킨다.
> 갱신 시키며 cnt값, 즉, 회의의 수를 누적시킨다.
반복문이 끝나면 누적된 cnt값을 출력한다.코드
#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
bool cmp(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(nullptr);
cout.tie(nullptr);
int N;
cin >> N;
vector<pair<int, int>> meeting(N);
for (int i = 0; i < N; i++) cin >> meeting[i].first >> meeting[i].second;
sort(meeting.begin(), meeting.end(), cmp);
int cnt = 0, end = 0;
for (auto& a : meeting)
{
if (a.first >= end)
{
cnt++;
end = a.second;
}
}
cout << cnt << '\n';
}
후기
문제를 잡고 한참을 생각해도 생각이 나지 않았다. 문제의 태그를 보니 그리디라고 되어있는데 왜 그리디인가 해서 그리디를 다시 봤다.
그리디란 가장 좋아보이는 최적의 선택을 하는것이다. 즉, 이 문제는 짧은 회의들을 최대한 끌어모아 최대한 많은 회의를 쳐내는게 목적이므로 그리디에 적합하다고 한다.
그건 그렇고 푸는 방식이 재밌다. 여러 정렬 방식을 생각했어도 끝시간을 기준으로 정렬하는건 생각하지 못했다.
생각해보면 끝나는시간이 빠른걸로 정렬하고 같다면 시작시간이 빠른걸로 정렬해야 시간 순서대로 정렬도 되고 또 빨리 끝날 수 있는 회의부터 정렬되어있는것이다.
이제 정렬이 끝났으니 끝나는 시간을 기준으로 잡고 이것으로 새로운 시작시간을 연결해주며 회의를 전부 다 돌면 끝나는 간단한 문제였다.
막상 하고나면 정말 쉽고 간단한데 도달하기까지 정말 어렵다.
