코딩 테스트 준비! (백준)/GREEDY

[그리디]백준 1931번 회의실 배정(C++)

lee-soo 2025. 5. 13. 19:49

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

 

그리디 알고리즘을 배운다면

무조건 나오는 문제 중 하나이다.

 

이건 그냥 외우다 시피 해라!~!

 

https://source-sc.tistory.com/59

 

[탐욕 알고리즘][2] - 회의실 배정 문제

유명한 Greedy 알고리즘 - 회의실 배정 문제 회의실 배정 문제는 그리디 알고리즘에서 빠지지 않고 등장하는 문제이다. 이문제는 각 회의마다 시작시간과 종료시간이 정해져있고 하나의 회의실에

source-sc.tistory.com

이 블로그에서 회의실 배정 문제에 대해 굉장히 자세히 알려주고 있다!

 

그리디 알고리즘을 사용하는 건 알겠는데 어떻게 사용하냐!

 

끝나는 시간을 기준으로 생각하면 된다

 

예를들어

 

q에 들어가는 회의 시간은

"종료 시간이 가장 빠른" 회의부터 들어가게 된다.

 

 

예를들어 

1 4

5 6

4 6 

이란 회의시간이 있고

 

정렬 된 상태는

1 4

4 6

5 6

이다.

그럼 4이후로 시작하는 회의가 

5 6

4 6

이 있다.

물론 직관적으로 보기에는 6 5 가 회의시간이 더 짧으니 이걸 선택하는 것은 좋지만

 

전체적으로 보자면 선택한 회의의 수는 똑같다

 

왜냐면 끝나는 시간을 기준으로 하는 것이기 때문에

 

그 사이에 빈 시간대에 대한 회의가 있었다면 이미 들어갔기 때문이다.

 

예를들어, 4~5라는 시간표가 있었다면 이미 들어갔을 것이다.

 

 

#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <utility>
using namespace std;

int main()
{
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> q;

    int n;
    cin >> n;
    for (int i = 0; i < n; i++)
    {
        int x, y; // 시작과 끝
        cin >> x >> y;
        q.push({y, x});
    }

    int count = 0;
    int e = 0;
    while (!q.empty())
    {
        int a, b;
        b = q.top().first;
        a = q.top().second;
        // cout << a << " " << b << "\n";
        if (e <= a)
        {
           
            count++;
            e = b;
        }
        q.pop();
    }

    cout << count << "\n";
}
 
그래서, 자동으로 끝나는 시간으로 오름차순 정렬을 하는 우선순위 큐를 생성해주었다.