[백준] 1931번 회의실 배정 C++ 풀이

---

알고리즘 분류

• 그리디 알고리즘
• 정렬

---

문제 설명

한 개의 회의실이 있는데 이를 사용하고자 하는 N개의 회의에 대하여 회의실 사용표를 만들려고 한다. 각 회의 I에 대해 시작시간과 끝나는 시간이 주어져 있고, 각 회의가 겹치지 않게 하면서 회의실을 사용할 수 있는 회의의 최대 개수를 찾아보자. 단, 회의는 한번 시작하면 중간에 중단될 수 없으며 한 회의가 끝나는 것과 동시에 다음 회의가 시작될 수 있다. 회의의 시작시간과 끝나는 시간이 같을 수도 있다. 이 경우에는 시작하자마자 끝나는 것으로 생각하면 된다.

---

입력 설명

첫째 줄에 회의의 수 N(1 ≤ N ≤ 100,000)이 주어진다. 둘째 줄부터 N+1 줄까지 각 회의의 정보가 주어지는데 이것은 공백을 사이에 두고 회의의 시작시간과 끝나는 시간이 주어진다. 시작 시간과 끝나는 시간은 231-1보다 작거나 같은 자연수 또는 0이다.

---

출력 설명

첫째 줄에 최대 사용할 수 있는 회의의 최대 개수를 출력한다.

---

예제 입력

11
1 4
3 5
0 6
5 7
3 8
5 9
6 10
8 11
8 12
2 13
12 14

---

예제 출력

4

---

아이디어

커스텀 비교 함수를 사용해서 pair의 second를 오름차순 정렬하고 second가 같다면 first를 기준으로 오름차순 정렬한다.

이렇게 정렬하면 회의가 끝나는 시간이 가장 짧은 순으로 정렬되므로 맨 처음 계산하는 값이 최대로 할 수 있는 회의이다.

---

알고리즘

pair가 들어있는 vector 선언

second를 기준으로 오름차순 정렬, second가 같다면 first를 기준으로 오름차순 정렬

vec[0]의 second를 기록하여

그 이후에 있는 값의 first가 second보다 작다면 회의 시간이 겹치므로 continue 해준다.

아니라면 그 값의 second를 새롭게 기록하고 count를 증가시키며 계산을 이어 나간다.

계산이 끝나면 count를 출력해 주면, 정답이다.

---

코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool cmp( pair<long long, long long> &v1,  pair<long long, long long> &v2)
{
    if(v1.second == v2.second) return v1.first < v2.first;
    else return v1.second < v2.second;
}
int main() {
    int n,cnt=1;
    cin>>n;
    vector<pair<long long, long long>> vec(n);
    for(int i=0;i<n;i++)
        {
            int a,b;
            cin>>a>>b;
            vec[i] = {a,b};
        }
    sort(vec.begin(), vec.end(), cmp);
    long long record = vec[0].second;
            for(int i = 1 ; i < n ; i++)
                {
                    if(vec[i].first < record) continue;
                    else
                    {
                        record = vec[i].second;
                        cnt++;
                    }
                }
    cout<<cnt;
    return 0;
}

---

후기

문제 링크 -> https://www.acmicpc.net/problem/1931

처음에는 pair의 first를 기준으로 오름차순 정렬을 했다.

그랬더니 한 번의 계산으로 끝나지 않고 모든 수를 순회하면서 더 높은 count가 나오는지 확인해야 했다.

그래서 시간 초과가 나왔다.

그 이후에도 first 기준 정렬을 버리지 못하고 여러 if 문을 추가하면서 시간을 줄이려고 노력했다.

그래도 계속 시간 초과가 나왔다.

 

두 번째로는 pair의 second를 기준으로 오름차순 정렬을 했다.

이렇게 정렬하니 맨 처음 계산한 값이 가장 많은 count가 나오는 것을 확인했다.

하지만 제출하니 계속 틀렸다.

 

회의가 끝나는 시간과 다른 회의가 시작하는 시간이 중복될 수 있으며

회의의 시작 시간과 끝나는 시간이 같은 회의도 존재할 수 있으므로

다른 정렬 기준이 필요했다.

 

마지막으로는 pair의 second를 기준으로 먼저 오름차순 정렬을 하고 만약 second가 같다면 first를 기준으로 오름차순 정렬을 진행했다. 이렇게 했더니 끝나는 시간이 같은 회의들은 시작하는 시간이 빠른 순서대로 정렬되어서 시간 중복의 경우에도 제대로 count를 증가시킬 수 있었다.

---

본 블로그의 모든 글은 개인적인 학습 내용이므로 다양한 오류가 있을 수 있습니다.

오류를 발견하신다면 해당 내용 댓글로 알려주시면 감사하겠습니다!