[Day 2] 백준 1931 : 회의실 배정

해법 : 정렬 후 greedy

사실 처음보고 무조건 DP로 짰다가 시간초과가 나와서 다시 생각해보았다.

해답은 회의가 끝나는 시간을 기준으로 오름차순 정렬한 뒤에 배열의 앞에서부터 보면서 조건에 맞는(회의 시작 시간이 내가 담은 회의들이 끝나는 시간이 크거나 같은 애들)을 담으면 된다.

 

왜 Greedy 가 해법일까?

조건에 맞는애가 있을 때 그 애를 선택하지 않고 다음 거를 선택했을 때 얻을 수 있는 이익이 없다. 즉, 현재 지점을 i라고 한다면 i대신 i+1을 선택했을 때(i+1도 조건에 맞는다고 가정하면) 얻는 이익이 없다는 것이다.

그 이유는 회의 종료 시간을 기준으로 정렬했기 때문에 i의 회의 종료 시간이 i+1의 회의 종료시간보다 작거나 같기 때문이다.

 

#include <iostream>
#include <cstdio>
#include <algorithm>

using namespace std;
int n;
struct tuple2 {
    long long s,e;
};
tuple2 A[100000+5];
//tuple2 table[100005];
bool sf(tuple2 a,tuple2 b) {
    if(a.e==b.e) {
        return a.s<b.s;
    } else {
        return a.e<b.e;
    }
}
int main()
{
    //freopen("input.txt","r",stdin);
    scanf("%d",&n);
    int i,j;
    for(i=0;i<n;i++) {
        scanf("%d %d",&A[i].s,&A[i].e);
    }
    sort(A,A+n,sf);
    int e=0;
    int cnt=0;
    for(i=0;i<n;i++) {
        if(A[i].s>=e) {
            cnt++;
            e=A[i].e;
        }
    }
    printf("%d\n",cnt);
    /*
    //DP 뻘 코딩
    table[0].s=1;
    table[0].e=A[0].e;
    int flag=0;
    for(i=1;i<n;i++) {
        j=i-1;
        flag=0;
        while(j>=0) {
            if(table[j].e<=A[i].s) {
                //printf("%d %d\n",j,table[j].s);
                if(table[j].s+1>table[i-1].s) {
                    //printf("0  : %d\n",i);
                    table[i].s=table[j].s+1;
                    table[i].e=A[i].e;
                } else {
                    //printf("1  : %d\n",i);
                    table[i].s=table[i-1].s;
                    table[i].e=table[i-1].e;
                }
                flag=1;
                break;
            }
            j--;
        }
        if(flag==0) {
            table[i].s=table[i-1].s;
            table[i].e=table[i-1].e;
        }
    }
    printf("%lld\n",table[n-1].s);*/
    return 0;
}