[백준] 13334번: 철로 (c++)

 

문제

---

집과 사무실을 통근하는 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 이다.

13334번: 철로

 

문제조건

---

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

 

풀이

---

처음에는 그냥 그리디하게 풀려고 했다. (h,o)쌍을 h을 기준으로 오름차순으로 정렬한 후 office 값을 확인하며 범위 안에 들어가는지 체크하려 했다. 하지만 문제가 집과 사무실의 위치가 모두 L에 포함되도록을 구하라 하였기 때문에 아래와 같은 반례가 발생한다.

끝 점을 기준으로 정렬을 하여도 반례가 너무 많았다. 방법을 모르겠어서 구글링을 해보니 라인 스위핑을 사용해야 하는 문제였다.

우선 끝 점을 기준으로 사람들을 정렬을 한다. 각 사람들이 조건을 만족하는지(end - start <=l)를 확인한다. 조건을 만족한다면 시작값을 우선순위 큐에 넣어준다. 이때 값이 작은 순서로 저장되게 하기 위하여 음수 값으로 저장하였다. 이후 가장 먼 시작점인(가장 작은 시작점)과 끝 점이 범위 안에 들어있는지 확인한다. 만약 범위 안에 들어있지 않다면 시작점을 바꿔준다(pq.pop()). 범위 안에 들어있다면 다음 사람을 확인한다.

 

코드

---

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

int n, l;
vector <pair<int, int>> people;
priority_queue <int> pq;
int answer = 0;

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() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		int h, o;
		cin >> h >> o;
		if (o < h) { people.push_back({ o,h }); }
		else { people.push_back({ h,o }); }
	}
	cin >> l;

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

	for (int i = 0; i < n; i++) {
		int start = people[i].first;
		int end = people[i].second;

		if (end - start > l) continue;
		pq.push(-start);

		
		while (!pq.empty()) {
			if (-pq.top() + l >= end) {
				break;
			}
			pq.pop();
		}

		answer = max(answer, (int)pq.size());
	}

	cout << answer;
}