[백준 13334] 철로 (C++)

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

문제

---

집과 사무실을 통근하는 n명의 사람들이 있다. 각 사람의 집과 사무실은 수평선 상에 있는 서로 다른 점에 위치하고 있다. 임의의 두 사람 A, B에 대하여, A의 집 혹은 사무실의 위치가 B의 집 혹은 사무실의 위치와 같을 수 있다. 통근을 하는 사람들의 편의를 위하여 일직선 상의 어떤 두 점을 잇는 철로를 건설하여, 기차를 운행하려고 한다. 제한된 예산 때문에, 철로의 길이는 d로 정해져 있다. 집과 사무실의 위치 모두 철로 선분에 포함되는 사람들의 수가 최대가 되도록, 철로 선분을 정하고자 한다.

양의 정수 d와 n 개의 정수쌍, (hi, oi), 1 ≤ i ≤ n,이 주어져 있다. 여기서 hi와 oi는 사람 i의 집과 사무실의 위치이다. 길이 d의 모든 선분 L에 대하여, 집과 사무실의 위치가 모두 L에 포함되는 사람들의 최대 수를 구하는 프로그램을 작성하시오.

그림 1. 8 명의 집과 사무실의 위치

그림 1 에 있는 예를 고려해보자. 여기서 n = 8, (h1, o1) = (5, 40), (h2, o2) = (35, 25), (h3, o3) = (10, 20), (h4, o4) = (10, 25), (h5, o5) = (30, 50), (h6, o6) = (50, 60), (h7, o7) = (30, 25), (h8, o8) = (80, 100)이고, d = 30이다. 이 예에서, 위치 10 과 40 사이의 빨간색 선분 L이, 가장 많은 사람들에 대하여 집과 사무실 위치 모두 포함되는 선분 중 하나이다. 따라서 답은 4 이다.

 

입력

---

입력은 표준입력을 사용한다. 첫 번째 줄에 사람 수를 나타내는 양의 정수 n (1 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 각 줄에 정수 쌍 (hi, oi)가 주어진다. 여기서 hi와 oi는 −100,000,000이상, 100,000,000이하의 서로 다른 정수이다. 마지막 줄에, 철로의 길이를 나타내는 정수 d (1 ≤ d ≤ 200,000,000)가 주어진다.

 

출력

---

출력은 표준출력을 사용한다. 길이 d의 임의의 선분에 대하여, 집과 사무실 위치가 모두 그 선분에 포함되는 사람들의 최대 수를 한 줄에 출력한다. 

 

문제 풀이

---

정렬 문제.

 

길이 d를 가진 선분안에 존재하는 선분의 개수가 최대값이 되려면 철로의 선분 시작점이 어떤 사람이 만들어내는 집-사무실 선분의 시작점이거나, 철로 선분 끝점이 어떤 사람이 만들어내는 집-사무실 선분의 끝점이어야 한다.

집과 사무실 위치를 만드는 선분 중 처음 지점에 대해 작은 순서대로 정렬하면 끝 지점에 대해서 판별할 수 없게 된다. 회의실 문제처럼 끝 지점이 작은 순서대로 정렬해준다. 철로의 선분 끝점을 집-사무실 선분의 끝점으로 잡으면, 철로의 시작점은 [집-사무실 선분의 끝점 - d]이다. 만약 집-사무실 선분의 시작점이 [ 집-사무실 선분의 끝점 - d]보다 작으면 해당 선분은 포함되지 않고, 크거나 같다면 해당 선분이 포함된다.

특정 선분이 포함되는지 확인하기 위해 자료구조를 사용해보자. 현재 끝 지점이 작은 순서대로 정렬되어 있고, 어떤 사람의 집-사무실 선분의 끝점이 철로의 선분 끝점이라고 정했다. 따라서 현재 탐색 중인 i번째 선분 을 포함하여 이전 선분에 대해 해당 선분들의 시작점이 [i번째 선분의 끝점 - d]보다 크거나 같은 선분의 개수들을 확인해주면 된다. 끝점이 작은 순서대로 스위핑하고 있으므로 [i번째 선분의 끝점 - d]의 값은 커지기 때문에 한 번 [i번째 선분의 끝점 - d]보다 작다고 확인된 선분은 또 다시 탐색할 필요가 없다. 따라서 한 번 아니라고 판단되면 이 선분을 탐색 대상에서 제외해주면 되고, 이에 따라 적절한 자료구조는 우선순위 큐가 된다.

다시 말해, 현재 탐색 중인 i번째 선분의 시작점을 우선순위 큐에 넣고, 큐가 빌 때까지 우선순위 큐의 top에 해당하는 원소가 i번째 선분의 끝점 - d보다 작으면 pop해주면 된다. 우선순위 큐에 남은 원소의 개수가 i번째 선분의 끝점을 철로의 끝점으로 삼았을 때 얻을 수 있는 값이 된다. 모든 집-사무실 선분에 대해 탐색해주고, 최댓값을 구하면 답이 된다.

 

아래는 코드.

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

bool cmp(pair<long long, long long>& p1, pair<long long, long long>& p2)
{
	if (p1.second < p2.second)
	{
		return true;
	}
	else if (p1.second == p2.second)
	{
		return p1.first < p2.first;
	}
	else
	{
		return false;
	}
}

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N;
	long long a, b, d;
	cin >> N;
	pair<long long, long long>* arr = new pair<long long, long long>[N];
	priority_queue<long long, vector<long long>, greater<long long>> pq;
	for (int i = 0; i < N; i++)
	{
		cin >> a >> b;
		if (a <= b)
		{
			arr[i] = pair(a, b);
		}
		else
		{
			arr[i] = pair(b, a);
		}
	}
	cin >> d;
	sort(arr, arr + N, cmp);
	int answer = 0;
	for (int i = 0; i < N; i++)
	{
		pq.push(arr[i].first);
		while (!pq.empty())
		{
			if (pq.top() < arr[i].second - d)
			{
				pq.pop();
			}
			else
			{
				break;
			}
		}
		answer = max(answer, (int) pq.size());
	}
	std::cout << answer << "\n";
	return 0;
}