.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";
}
그래서, 자동으로 끝나는 시간으로 오름차순 정렬을 하는 우선순위 큐를 생성해주었다.
'코딩 테스트 준비! (백준) > GREEDY' 카테고리의 다른 글
[그리디]백준 1201번 NMK(C++) (0) | 2025.05.15 |
---|---|
[그리디]백준 1744번 수 묶기(C++) (0) | 2025.05.15 |
[그리디]백준 1541번 잃어버린 괄호(C++) (0) | 2025.05.15 |
[그리디]백준 11047번 동전 0 (C++) (0) | 2025.05.13 |
[Greedy] 백준 10972번 다음 순열 (C++) (0) | 2025.04.08 |