백준 1931 회의실 배정 C++

핵심

• 최대한 많은 수의 회의를 하기 위해서는 먼저 회의가 끝나는 시간을 기준으로 정렬을 하고 끝나는 시간이 최솟값인 회의를 초기값으로 시작한다.
• 위 기준에 맞춰 한번에 정렬하기 위해 끝나는 시간과 시작하는 시간 순서로 pair 배열 변수에 담는다.
• sort함수를 이용해서 정렬
• for문을 돌려 첫 회의의 끝나는 시간보다 큰 값을 가지는 회의의 시작 시간을 찾고, 그 시작시간을 갖는 값의 끝나는 시간을 업데이트 해주고 회의의 수를 더해준다.

구현

#include <bits/stdc++.h>
using namespace std;
#define X first
#define Y second

pair<int, int> arr[100002];

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    int n; cin >> n;
    // 끝나는 시간을 기준으로 정렬해야 하기 때문에 끝나는 시간을 앞에 둔다.
    for(int i = 1; i <= n; i++) {
        int a, b; cin >> a >> b;
        arr[i] = {b, a};
    }
    // 끝나는 시간, 시작하는 시간을 기준으로 정렬
    sort(arr+1, arr+n+1);
    
    // 제일 먼저 시작하는 회의는 끝나는 시간이 최솟값인 회의의다. 
    // 그래서 arr[1]의 값을 초기값으로 시작한다.
    int ans = 1;
    int endTime = arr[1].X;
    for(int i = 2; i <= n; i++) {
    	// endTime이 현재 회의의 시작시간보다 크면 continue
        if(endTime > arr[i].Y) continue;
        // ans와 endTime update
        ans++; endTime = arr[i].X;
    }
    cout << ans;
}

후기

처음부터 모든 경우의 수를 구하는 것이 아니라 가장 최적인 방법을 이용해서 풀이를 하는 그리디 알고리즘의 문제였다.