알고리즘/Baekjoon
[PS] 철로 / C++ (백준 13334번)
dh_0e
2025. 3. 13. 00:36
정렬과 priority queue만 적절히 사용할 줄 알면 쉽게 풀리는 문제
- 사람들의 집과 사무실의 위치는 바뀌어도 상관 없으므로 first 값이 작도록 설정한 뒤, second 값을 기준으로 오름차순 정렬해줌 (second 값이 같을 경우 first 값 오름차순으로)
- 차례대로 우선순위 큐 top에 있는 사람을 기준으로 범위 안에 들어가는 지 확인
- O: 우선순위 큐에 i번째 사람 추가, 범위 안에 있는 사람 수가 max인 지 확인
- X: 범위 안에 들어갈 때까지 top에 있는 사람을 pop해줌
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
pair<int, int> d[1000001];
priority_queue<pair<int, int> > prique;
bool cmp(const pair<int, int> & a, const pair<int, int> & b)
{
if (a.second == b.second) {
return a.first < b.first;
}
return a.second < b.second;
}
int main()
{
int n, k, max = 0;
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int a, b;
scanf("%d %d", &a, &b);
if (a > b) {
int c = a;
a = b; b = c;
}
d[i].first = a;
d[i].second = b;
}
scanf("%d", &k);
sort(d + 1, d + n + 1, cmp);
for (int i = 1; i <= n; i++) {
if (d[i].first + k < d[i].second)continue;
while (prique.size() > 0) {
if ( - prique.top().first + k < d[i].second) {
prique.pop();
}
else break;
}
prique.push(make_pair(-d[i].first, -d[i].second));
if (prique.size() > max)max = prique.size();
}
printf("%d\n", max);
return 0;
}