백준 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 이다.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면 사람들의 집과 사무실의 위치가 일직선에 위치하며 철로의 길이 D가 주어졌을 때 철로 안에 집과 사무실이 모두 위치한 사람이 최대가 되게끔 철로를 놓았을 때 포함시키는 수를 구하면 된다.

 

해당 문제를 풀기 위해서는 정렬 조건을 잘 설정해야 한다.

우선 간단하게 생각해 보자.

빨리 시작되는 기준으로 정렬을 진행하고 시작점에 D를 더해 철로를 만든다고 가정해 보자.

이를 $end = h+D$로 표현했을 때 end보다 빨리 끝나는 개수를 셀 수 있다.

하지만 이렇게 되면 배열의 정렬 기준을 세우기 까다롭다.

빨리 시작하는 경우를 우선으로 하고 있기 때문에 end보다 빨리 끝나는 경우가 순서대로 주어질 것이라는 보장이 없다.

따라서 이 정렬 기준은 정답을 구할 수 없다.

 

이를 반대로 생각해 빨리 끝나는 기준으로 정렬을 해보자.

bool cmp(pair<int, int>& a, pair<int, int>& b)
{
    if (a.second == b.second) return a.first < b.first;
    return a.second < b.second;
}

그리고 끝나는 시점을 기준으로 D만큼 빼 시작점을 설정해 보자.

이를 $start = o - D$로 표현하고 start보다 시작점이 크거나 같은 경우는 철로에 포함시킬 수 있게 된다.

빨리 끝나는 기준으로 정렬되어 있기 때문에 다음에 나오는 경우는 무조건 지금보다 늦게 끝난다.

즉, 이전까지 등장한 경우는 시작점만 start보다 크거나 같다면 무조건 철로에 포함시킬 수 있게 된다.

따라서 기준점을 하나씩 옮겨가며 이를 확인하면 된다.

 

이를 쉽게 구현하기 위해 우선순위 큐를 사용할 수 있다.

우선순위 큐에서는 빨리 끝나는 수가 먼저 나올 수 있게 최소 힙으로 설정하고 시작점을 저장한다.

priority_queue<int, vector<int>, greater<int>> pq;

그리고 기준점보다 빨리 시작한 경우를 모두 제외하고 진행하며 우선순위 큐에 담겨있는 요소의 최댓값을 구하면 정답을 구할 수 있다.

for (auto& [h, o] : routes)
{
    start = o - D;

    while (!pq.empty() && pq.top() < start) 
    {
        pq.pop();
    }

    if (h >= start) 
    {
        pq.push(h);
        ans = max(ans, (int)pq.size());
    }
}

 

정렬 기준을 만약 반대로 설정하는 것도 가능하다.

늦게 시작하는 기준으로 정렬한 뒤 시작점에 D를 더하고 끝나는 지점을 저장하며 반대로 진행하는 것도 가능하다.

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>
#include <unordered_set>
using namespace std;
#define INPUT_OPTIMIZE cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define INF 2e9

using namespace std;
int N, D;
vector<pair<int, int>> routes;

bool cmp(pair<int, int>& a, pair<int, int>& b)
{
	if (a.second == b.second) return a.first < b.first;
	return a.second < b.second;
}

int main()
{
	INPUT_OPTIMIZE;
	
	cin >> N;

	for (int i = 0; i < N; i++)
	{
		int h, o;
		cin >> h >> o;
		if (o < h) swap(h, o);
		routes.push_back({ h, o });
	}

	cin >> D;

	sort(routes.begin(), routes.end(), cmp);

	int start = 0;
	priority_queue<int, vector<int>, greater<int>> pq;
	int ans = 0;

	for (auto& [h, o] : routes)
	{
		start = o - D;

		while (!pq.empty() && pq.top() < start) 
		{
			pq.pop();
		}

		if (h >= start) 
		{
			pq.push(h);
			ans = max(ans, (int)pq.size());
		}
	}
	
	cout << ans;

	return 0;
}

---