백준 1931번 - 회의실 배정

백준 1931번 문제 바로가기

문제를 잘못 이해하는 것에서부터 풀어내는 데에 시간이 꽤나 많이 걸렸던 문제. 처음에는 여러 개의 회의실로 착각해서 아예 풀이 방향이 달랐고, 다음에는 “모든 경우의 수를 고려해야하나?” 고려하다보니 문제를 푸는 것이 어려웠다.

이 문제를 해결하는 방법의 주요 포인트를 시작시간이 아닌 종료 시간을 기준으로 정렬하자는 것이었다. 종료 시간을 기준으로 정렬하게 되면 같은 시간대에 최대한 많은 횟수의 회의를 열 수 있기 때문이다. 지금까지 풀어온 greedy 문제와는 결이 조금 달라서 당황을 많이했는데, 경험치를 더 늘려나가자!

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    int N;
    vector<pair<int, int>> meeting;
    int curr_time=0;
    int count=0;
    
    cin >> N;
    for (int i=0; i<N; i++){
        int start, end;
        cin >> start >> end;
        meeting.push_back(make_pair(end, start));
    }
    
    sort(meeting.begin(), meeting.end());
    
    for (int i=0; i<N; i++){
        if (curr_time <= meeting[i].second){
            curr_time = meeting[i].first;
            count++;
        }
    }
    
    cout << count;

    return 0;
}

Comments: