백준) 1931 회의실배정

1931 회의실배정

문제

한 개의 회의실이 있는데 이를 사용하고자 하는 n개의 회의들에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 최대수의 회의를 찾아라. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

입력

첫째 줄에 회의의 수 n(1<=n<=100,000)이 주어진다. 둘째 줄부터 n+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

출력

첫째 줄에 최대 사용할 수 있는 회의 수를 출력하여라.

예제 입력 

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

예제 출력 

4

1. 접근

주어진 조건 속에서 최대한 많은 회의를 골라야 한다. 그리디 알고리즘을 선택.

또는 각 회의를 넣을지 말지 2^n으로 탐색하거나,

동적 계획법으로 풀 수도 있다.

끝나는 시간순으로 회의들을 저장하는 confer[]배열을 정렬한 다음

ans(idx) = confer[idx] or 이전에 끝나는 회의들 중 최대한으로 선택할 수 있는 회의의 수 라는 함수를 만들자.

그러면 매 단계에서 ans()는 confer[idx]를 고를지 여부를 결정한다.

고른다면 confer[idx]가 될 것이고, 아니라면 1+ans(이전에 선택한 회의의 번호)가 되겠다.

2. 풀이

끝나는 시간 순으로 회의들을 정렬한 다음,

처음부터 회의들을 순회하면서 수행가능한 회의들로 갱신해 나간다.

3. 코드

#include <stdio.h>
#include <algorithm>
using namespace std;
 
typedef pair<int, int> p;
p confer[100000];
int n, i, m, cnt;
 
int main() {
    scanf("%d", &n);
    for (i = 0; i < n; ++i)
        scanf("%d %d", &confer[i].second, &confer[i].first);
    sort(confer, confer + n);
    cnt = 0;
    for (i = 0; i < n; ++i) {
        if (confer[i].second >= m) {
            cnt++;
            m = confer[i].first;
        }
    }
    printf("%d", cnt);
    return 0;
}

4. 후기

그리디로 풀 수 있는 문제는 대부분 동적 계획법으로 풀 수 있다고 한다.

모든 단계를 고려하는 동적 계획법과 최적해만 고려하는 그리디는 본질적으로 같다.

다만 동적 계획법이 더 오래 걸리기 때문에 그리디를 사용한다.