[Algorithm] Baekjoon 1931번 : 회의실 배정

https://www.acmicpc.net/problem/1931

1931번: 회의실 배정

 

struct Node
{
    int start;
    int end;
};
 
bool cmp(const Node& a, const Node& b)
{
    if (a.end == b.end) return a.start < b.start;
    return a.end < b.end;
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int n = 0;
    int a, b;
    int count = 0;
    vector<Node> v;
 
    cin >> n;
 
    for (int i = 0; i < n; i++)
    {
        cin >> a >> b;
        v.push_back({ a,b });
    }
 
    sort(v.begin(), v.end(), cmp);
 
    int end = v[0].end;
 
    for (int i = 1; i < n; i++)
    {
        if (end <= v[i].start)
        {
            count++;
            end = v[i].end;
        }
    }
 
    cout << count + 1;
}

어떻게 기준을 잡느냐가 중요한 전형적인 그리디 문제이다.

완전탐색으로도 풀 수는 있겠지만, 문제에 허용된 시간제한을 보면 아니라고 생각이 들 것이다.

시작시간을 기준으로 오름차순정렬을 해서 노드를 포함하려고 할 경우, 해당 노드의 회의시간이 길어버린다면 최적의 해가 되지 않는다. 즉, 경우의 수가 있고 이 경우의 수를 생각하다보면 완전탐색이 되버려서 시간초과가 난다. 

딱 내가 그랬다.

 

그렇기 때문에 시작시간이 아니라, 종료시간을 기준으로 문제를 접근해야 한다.

문제해결을 위한 로직은 다음과 같다.

 

1. 종료시간 기준으로 오름차순 정렬. 단, 종료시간이 같다면 시작시간 기준으로 오름차순해준다.

2. 다음 노드 시작시간이 현재노드 종료시간보다 크다면 count++ 해주고, 해당노드를 기준노드로 선택.

 

기본적으로 각 회의간 텀이 짧아야 최대한 많은 회의를 우겨넣을 수 있다.

그것에 대한 표현으로 시작시간을 기준으로 오름차순해서 접근할 수 있지만, 이미 말했다시피 선택된 회의의 회의시간이 너무 길어버리면 이후에 선택할 수 있는 회의의 개수가 극히 제한되버린다.

 

그렇기 때문에 다른 표현을 이용해야하는데, 그게 바로 종료시간기준으로 오름차순정렬을 한 것이다.

이렇게 순서는 맞춰놨으니 앞에서부터 하나씩 탐색하면서 조건만 맞는다면 바로 집합에 포함시키면 되고, 그게 정답이라고 보장되어진다. 조건은 위에 적어놓은 2번이다.

 

위 로직대로 행했을 때 선택한 회의는 아래와 같다.

-> 텀이 제일 짧은 회의이면서(로직 1번), 종료 이후 시작까지 가장 빠른 회의(로직 2번)

 

이런 회의만 선택해서 포함시키기 때문에, 최대한 많은 회의를 집어넣을 수 있게 된다.