백준 1931_회의실 배정

문제 링크

** 문제한줄요약 **

주어진 시간 내 최대 회의 수를 구해라. (회의간 겹치지 않음, i-1번째 끝나는 시간 = i번째 시작 시간, 중단되지 않음)

내가 생각한 조건

일단 회의시간을 일정 기준에 맞게 정렬한 뒤 해당 회의에서 가장 가까운 회의들을 순차적으로 비교하면서 카운트하면 답이 나올 것이라 생각했다. 즉, 해당 회의에서 가장 나은 선택을 하는 것이므로 그리디 알고리즘을 사용하는 게 나을 것 같다고 생각했다.
처음에 시작 시간을 기준으로 정렬해서 조건을 따지려고 했었다. 그러나 시작 시간으로 정렬하여 고민한 결과 i번째 회의 다음에 올 수 있는 모든 회의의 경우의 수를 넣어 계산해야 할 것 같았고, 그러면 너무 비효율적으로 계산되는 생각이 들었다. 그리고 계속 고민하다 방법이 잘 생각나지 않아 블로그를 참조했다.

작성한 코드

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
 
int main()
{
    int n;
    vector< pair < int, int > > v;
 
    cin >> n;
 
    for(int i = 0; i < n; i++)
    {
        int start, end;
        cin >> start >> end;
        v.push_back(make_pair(end, start));
    }
 
    sort(v.begin(), v.end());
 
    int end_min = v[0].first;
    int ans = 1;
 
    for(int i = 1; i < n; i++)
    {
        if(end_min <= v[i].second)
        {
            ans += 1;
            end_min = v[i].first;
        }
    }
    cout << ans << '\n';
}

피드백

이 문제의 포인트는 종료 시간이 중요하다는 것이다. 시작 시간이 아무리 빨라도 종료 시간이 늦으면 최대 회의 개수를 구할 수 없기 때문이다.
그래서 종료 시점에 대한 정렬을 시도했다.

기준점이 종료시간이므로 최소의 종료시간인 0번째 회의의 종료시간을 최초의 기준점으로 잡는다.
그리고 i번째 기준점(종료시간)을 i+n번째 시작시간과 비교하여 종료시간이 시작시간보다 작을 경우 i번째 종료시간을 i+n번째 종료시간으로 대치시키면 된다.

한줄평

최대/최소를 구할 때 시작점/앞쪽 값만 기준으로 하는 것이 아닌 뒤쪽을 기준으로 하는 경우를 생각하자.
모든 문제가 그랬듯 문제에 주어진 조건들 중에 답이 있다.