[BAE/<JOON> 문제풀이] 13334. 철로

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

13334번: 철로

핵심::
문제 카테고리가 라인 스윕이고 정확한 풀이 로직이 정해져 있지 않아서 핵심을 정확하게 뭐라고 쓰기 애매하다.

강의실 문제와 비슷하여 해당 문제 풀이에서 영감을 받았다.

풀이::
라인 스위핑은 기본적으로 주어진 배열 정렬하고 순회하며 답을 찾는 알고리즘을 의미한다.


시작 위치는 편의상 출근길의 시작 지점으로 고정한다. 

주어진 L보다 출근길의 거리가 멀 경우 탐색에서 제외한다.

남은 출근길을 도착 지점을 기준으로 정렬한다.

현재 L에 포함된 출근길들은 시작 지점을 기준으로 정렬한다.

포함된 출근길들은 우선순위 큐를 사용하여 정렬한다.

만약 현재 출근길이 현재 포함된 출근길의 시작 지점과의 거리가 L 초과일 경우 L 이하가 될 때 까지 포함된 출근길 앞부터 요소를 제거한다( 우선순위 큐 사용 ).

현재 출근길을 포함된 출근길에 추가하고 포함된 출근길 개수를 확인해 최댓값을 갱신한다.

위의 로직으로 하나의 출근길에 대해서 거리가 L 이하인 가장 먼 출근길들을 모두 확인하고 갱신 할 수 있다.

의견::
라인 스윕 문제들은 뭔가 그리디 같으면서 DP같기도 하고..

이런 문제는 진짜 태그 안보면 삽질 엄청할 것 같다.

 

코드::

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

struct line {
	int s, e;
};

struct cmp {
	bool operator()(line a, line b) {
		return a.s > b.s;
	}
};

bool cmpa(line a, line b) {
	return a.e < b.e;
}

int main()
{
	int n;
	cin >> n;
	priority_queue<line, vector<line>, cmp> pq;
	vector<line> arr(n + 1);
	for (int i = 1; i <= n; i++) {
		int s, e;
		cin >> s >> e;
		arr[i].s = s < e ? s : e;
		arr[i].e = s > e ? s : e;
	}
	int m;

	sort(arr.begin() + 1, arr.end(), cmpa);

	cin >> m;	
	
	int mx = 0;

	int base = 1;
	while (base <= n && arr[base].e - arr[base].s > m) base++;	
	if (base > n) {
		cout << 0;
		return 0;
	}
	pq.push(arr[base]);

	for (int i = base + 1; i <= n; i++) {
		if (arr[i].e - arr[i].s > m) continue;
		while (!pq.empty() && arr[i].e - pq.top().s > m) {
			pq.pop();
		}
		pq.push(arr[i]);
		mx = mx > pq.size() ? mx : pq.size();
	}

	cout << mx;

	return 0;
}