[C++]Baekjoon 1931번: 회의실 배정

1. 문제

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

1931번: 회의실 배정

 

N개의 회의에 대해서 회의의 시작 시간과 종료 시간이 주어졌을 때,

 

각 회의가 겹치지 않게 회의실을 이용할 수 있는 최대 회의의 개수를 구하는 문제이다.

 

회의실의 수는 1개이고, 회의가 종료되는 것과 동시에 다음 회의가 시작될 수 있다.

2. 풀이

먼저 시작하더라도 늦게 끝난다면 그 회의는 선택될 수 없다.

 

즉, '종료 시간'이 이 문제의 주인공임을 알 수 있다.

 

남은 회의 중 종료 시간이 가장 빠른 회의의 시작 시간이 직전 회의의 종료 시간 이후라면 그 회의를 선택해 주면 된다.

 

우선, 각 회의의 시작 시간, 종료 시간을 입력받고 이를 종료 시간이 빠른 순서대로 정렬해주자.

 

정렬을 위해서 #include <algorithm>을 포함해주고, 정렬을 편하게 하기 위해서 (end, start)의 순서로 벡터에 넣어주자.

 

현재 시간을 첫번째 회의의 종료 시간 time[0].first으로 해주고,

 

만약 그다음으로 빨리 끝나는 회의의 시작 시간time[i].second이 현재 시간 이 후라면,

 

그 회의를 진행한다는 의미로 cnt++을 하고, 현재 시간을 그 회의의 종료 시간 time[i].second로 갱신해주면 된다.

3. 코드

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

int main() {

    int rep;

    int start, end; // 회의의 시작 시간, 끝나는 시간

    int now; // 현재 시간

    int cnt = 1; // 회의의 개수를 세 줄 변수

   

    vector<pair<int, int>> time;

    cin >> rep;

    for (int i = 0; i < rep; i++) {

        cin >> start >> end;

        time.push_back(make_pair(end, start)); // end 를 먼저 넣어서 정렬에 용이하게 한다

    }

    sort(time.begin(), time.end()); // 정렬, #include <algorithm> 필수!

    now = time[0].first; // 첫번째 회의가 종료된 시간부터 계산

    for (int i = 1; i < rep; i++) {

        if (now <= time[i].second) { // 지금 시간 이 후에 시작 된 회의라면 OK

            cnt++;

            now = time[i].first; // 현재시간을 이 회의의 종료 시간으로 갱신

        }

    }

    cout << cnt;

    return 0;

}

4. 느낀점

와 정말 어렵게 풀었다... 정답으로 가는 풀이법 자체를 늦게 찾아낸 것도 있지만, 

 

중간에 생각이 한번 잘못 가서 엉뚱한 곳에서 계속 고민하고 있었다. (종료 시간이 같은 회의라면 그중에서 하나의 회의만 진행될 수 있는데, 그들을 한 번 더 정렬하려고 했었다. 정말 바보 같았다.)

 

회의실 문제는 전형적인 그리디 알고리즘을 활용하는 문제이다.

 

각 단계에서 가장 좋은 선택을 하면 정답을 구할 수 있기 때문이다.

 

이 문제를 통해서 sort()를 사용할 때는 #include <algorithm> 을 까먹지 않아야 한다는 것을 상기할 수 있었고,

 

vector에 <int, int> 처럼 인자를 쌍으로 저장하려고 할 때, pair<int, int>를 사용해야 하는 이유를 자세하게 알아보았다.

 

pair는 두 값을 하나의 묶음으로 사용할 수 있게 해주는 C++ 표준 라이브러리의 클래스이다.

 

vector의 인자는 한 종류의 타입만을 지정할 수 있다.

 

즉, vector의 타입은 vector<T>와 같이 단일한 형태여야 한다.

 

그렇기 때문에 'pair'를 사용하여 두 가지 이상의 값을 하나의 객체로 묶어준다.

 

push_back() 역시 하나의 인자만을 받아야 한다.

 

그렇기 때문에 push_back(make_pair(end, start))로 pair 객체를 생성하여 벡터에 추가한다.

 

make_pair는 두 개의 값을 가지고 pair로 묶어주는 편리한 함수이다.

 

make_pair(a, b)는 'pair<int, int>를 생성한다.

 

평소에는 이유도 모르고 사용했는데 좀 더 자세히 파고들 계기가 되어준 문제였다.

 

오늘 하루도 쌓였다!