백준 1931_회의실 배정.cpp

<소스코드>

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int main(){
    int n;
    cin >> n;
    int begin[n]; int end[n];
    vector<pair<int,int>> order;
    for(int i = 0; i < n; i++){
        cin >> begin[i] >> end[i];
    }
    for(int i = 0; i < n; i++){
        order.push_back(make_pair(end[i],begin[i]));
    }
    sort(order.begin(),order.end());
    int earliest = 0; int selected = 0;
    for(int i = 0; i < n; i++){
        int meetingBegin = order[i].second;
        int meetingEnd = order[i].first;
        if(earliest <= meetingBegin){
            earliest = meetingEnd;
            selected++;
        }
    }
    cout << selected << endl;
    return 0;
}

1. 변수&함수
   int n : 회의의 수
   int begin[n], end[n] : 각 회의의 시작과 끝 시간
   vector<pair<int,int>> order : 회의의 시작과 끝 시간을 mapping한 벡터
   int earliest : 가장 빨리 끝나는 회의
   int selected : 선택된 회의의 수
   int meetingBegin, meetingEnd : 각 회의의 시작과 끝나는 시간

2. 알고리즘
   1) pair을 이용하여 회의 시작시간과 회의 끝시간을 묶어서 벡터에 저장한다.
   2) 회의의 끝나는 시간을 기준으로 정렬한다.
   3) 회의가 끝나는 시간에 가장 가까운 회의가 시작하는 값을 찾고, earliest는 그 회의가 끝나는 시간으로 설정한다
   4) selected를 출력한다.

3. 배운점
   1) pair<[type1],[type2]> p
   : 사용할 데이터 타입1,2를 넣고 그 타입의 pair 클래스인 p를 만듬
   2) p.fisrt, p.secode : 첫번째인자, 두번째인자
   3) make_pair(변수1,변수2)
   : 변수 1, 변수 2가 들어간 pair를 만들어줌

4. 아쉬운점&느낀점
   사실 책으로 공부하면서 봤던 알고리즘이여서 쉽게 해결할 수 잇었다. 그리디 알고리즘은 일단 그리디 알고리즘이라는 것을 깨달으면 그 다음 해결은 쉬운거 같다. 그리디 알고리즘을 사용할 수 있는지를 잘 확인해야겠다.