백준 1931. 회의실배정 [실패]

1.실패 원인

코로나로 인해서 알고리즘 수업을 제대로 듣지 않았던 탓인지.. 스케쥴 짜기는 분명 그리디 기본 문제였는데도 생각이 나지 않았다. 문제를 이해하는 건 어렵지 않았지만 순서를 정하는 방법을 한참을 고민해도 답이 나오지 않았다. 시작시간과 회의시간만 생각을 했는데 끝나는 시간을 기준으로 정렬을하여 답을 채택하다가 같이 끝나는 시간의 회의는 시작시간을 기준으로 선택을 한다는 것에 뒷통수가 얼얼했다. 

 

2.작성 코드

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

int N; //<=100000

int cBegin[100000], cEnd[100000]; //conference 시작시간, 끝나는 시간

 

//탐욕법을 사용

//제일 먼저 시작하는 회의를 선택하고 그와 겹치는 회의들 제외

//첫번째 회의가 끝나고 제일 빨리 시작하는 다음 회의를 선택하고 겹치는 회의들 제외

int schedule(void)

{

        //일찍 끝나는 순서대로 정렬

        vector<pair<int, int>> order;

        for (int i = 0; i < N; i++)

               order.push_back(make_pair(cEnd[i], cBegin[i]));

        sort(order.begin(), order.end());

        //earliest: 다음 회의가 시작할 수 있는 가장 빠른 시간

        //selected: 지금까지 선택한 회의의 수

        int earliest = 0, selected = 0;

        for (int i = 0; i < order.size(); i++)

        {

               int meetingBegin = order[i].second, meetingEnd = order[i].first;

               if (earliest <= meetingBegin)

               {

                       //earliest를 마지막 회의가 끝난 시간 이후로 갱신

                       earliest = meetingEnd;

                       selected++;

               }

        }

        return selected;

}

 

int main(void)

{

        cin >> N;

 

        for (int i = 0; i < N; i++)

               cin >> cBegin[i] >> cEnd[i];

 

        cout << schedule() << endl;

        return 0;

}



출처: https://jaimemin.tistory.com/391 [꾸준함]

3.참고 코드

https://jaimemin.tistory.com/391

백준 1931번 회의실배정

 

4. 해결 방안

회의실배정 문제 같은 경우에는 명확한 풀이 방법이 제시되어 있다. 하나의 유형이라고 생각하고 어떤식으로 정렬을 먼저 해야하는지를 숙지해야겠다.