이번에는 백준 1931번 회의실 배정 문제를 풀어보았습니다.
문제를 처음 봤을 때 최대한 많은 회의를 선택해야 하므로, 가장 빨리 끝나는 회의를 먼저 선택하는 것이 항상 유리하다고 생각했습니다.
그래서 회의를 종료 시간 기준으로 정렬한 뒤, 현재 시간 이후에 시작할 수 있는 회의만 선택하는 그리디 방식으로 구현하였습니다.
문제 설명
회의마다 시작 시간과 종료 시간이 주어집니다.
회의실은 하나뿐이며, 동시에 두 개 이상의 회의를 진행할 수 없습니다.
회의실을 사용할 수 있는 회의의 최대 개수를 구하는 문제입니다.
풀이 아이디어
먼저 모든 회의를 종료 시간 기준으로 오름차순 정렬하였습니다.
현재 시간이 다음 회의의 시작 시간보다 작거나 같다면 해당 회의를 선택하였습니다.
회의를 선택하면 현재 시간을 그 회의의 종료 시간으로 변경하였습니다.
이 과정을 모든 회의에 대해 반복하면 선택 가능한 최대 회의 개수를 구할 수 있습니다.
코드
#include <bits/stdc++.h>
using namespace std;
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
int n;
cin >> n;
vector<pair<int, int>> inp;
for (int i=0; i<n; i++) {
int st,ed;
cin >> st >> ed;
inp.push_back({ed,st});
}
sort(inp.begin(), inp.end());
int t = 0;
int ret = 0;
for (pair<int, int> next : inp) {
if (next.second >= t) {
ret++;
t = next.first;
}
}
cout << ret;
return 0;
}풀이 흐름
- 모든 회의를 입력받습니다.
- 종료 시간 기준으로 오름차순 정렬합니다.
- 현재 시간 이후에 시작 가능한 회의를 확인합니다.
- 선택 가능한 회의라면 개수를 증가시키고 현재 시간을 종료 시간으로 갱신합니다.
- 모든 회의를 확인한 뒤 선택한 회의 개수를 출력합니다.
구현 포인트
1. 종료 시간 기준 정렬
회의를 종료 시간 기준으로 정렬하였습니다.
inp.push_back({ed, st});
sort(inp.begin(), inp.end());pair를 (종료 시간, 시작 시간) 형태로 저장하였기 때문에 종료 시간이 빠른 순으로 자동 정렬됩니다.
종료 시간이 같은 경우에는 시작 시간이 빠른 순으로 정렬됩니다.
2. 현재 시간 관리
현재 회의가 끝난 시간을 t로 관리하였습니다.
int t = 0;회의를 하나 선택하면 현재 시간을 해당 회의의 종료 시간으로 갱신하였습니다.
t = next.first;3. 회의 선택
현재 시간이 회의 시작 시간보다 작거나 같다면 해당 회의를 선택할 수 있습니다.
if (next.second >= t) {
ret++;
t = next.first;
}회의 하나를 선택하면 회의 개수를 증가시키고 현재 시간을 갱신하였습니다.
4. 그리디 선택
이 문제의 핵심은 가장 빨리 끝나는 회의를 먼저 선택하는 것입니다.
종료 시간이 빠른 회의를 먼저 선택해야 이후에 선택할 수 있는 회의가 최대가 됩니다.
따라서 종료 시간 기준으로 정렬한 뒤 가능한 회의를 차례대로 선택하는 그리디 전략으로 최대 회의 개수를 구할 수 있었습니다.
