[BOJ/13334] 철로, c++

🔗 링크

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

13334번: 철로

https://github.com/jokj624/PS/blob/master/10000-15000/13334.cpp

jokj624/PS

 

🤯 한줄 후기

너 - 무 어렵다. 반례만 찾다 실패

🤷 문제

👩‍💻 풀이

대충 수직선 상 좌표가 있을 때, 철로 길이 d로 가장 많이 포함 할 수 있는 좌표 개수를 찾으면 되는 문제이다.

처음 생각한 방법은 정말 그리디하게 

우선순위 큐에서 x좌표 순서대로 정렬한 후, x가 같을 시 y좌표 순서대로 정렬해준다.

그리고 x-y 좌표 차이가 d보다 작다면

 

1. start-end 가 없을 때 start-end를 각 각 현재 x-x+d 로 갱신해줬다. 

2. start-end 가 존재할 때, 현재 좌표가 그 안에 있는지 확인

   2-1. 안에 있다면 카운팅

   2-2. 안에 없다면 start-end 새로 갱신

 

뭐 이런 방법이다. WA만 엄청 받았다. 틀린 코드는 아래에!

//WA
//BOJ 13334 철로
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
#include <limits.h>
using namespace std;
typedef long long ll;
struct point {
	int x;
	int y;
};
struct compare {
	bool operator()(const point& p1, const point& p2) {
		if(p1.x == p2.x)	return p1.y > p2.y;
		else	return p1.x > p2.x;
	}
};
bool cmp(const point& p1, const point& p2){
	return p1.x < p2.x;
}
priority_queue<point, vector<point>, compare> pq;
int main()
{
	int N;
	vector<point> v;
	cin >> N;
	for(int i=0; i<N; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		v.push_back({a, b});
		if(v[i].x > v[i].y)	swap(v[i].x, v[i].y);
	}
	int d;
	cin >> d;
	sort(v.begin(), v.end(), cmp);
	for(point tmp: v){
		pq.push(tmp);
	}
	ll start = LLONG_MAX, end = LLONG_MAX;
	int ans = 0, count = 0;
	while(!pq.empty()){
		point current = pq.top();
		pq.pop();
	//	cout << current.x << " " << current.y << endl;
		if((current.y - current.x) > d ) 	continue;
		if(start == LLONG_MAX || end == LLONG_MAX){
			start = current.x;
			end = current.x + d;
			count += 1;
			ans = max(ans, count);
		}
		else{
			if(current.x >= start && current.y <= end){
				count += 1;
				ans = max(count, ans);
			}
			else{
				start = current.x;
				end = current.x + d;
				ans = max(count, ans);
				count = 1;
			}
		}
	}
	printf("%d", ans);
	return 0;
}

 

반례를 고쳐도 계속 틀려 너무 힘들었다. 결국 풀이를 봤는데 우선순위 큐 2개를 사용하는 풀이였다.

 

처음 우선순위 큐에는 도착점을 기준으로 정렬

두번째 우선순위 큐는 시작점을 기준으로 정렬 

 

처음 큐에는 미리 모든 좌표를 넣어놓고 해당 큐에 원소가 없을때 까지 거리 비교를 해 두번째 큐에 삽입한다.

 

처음 큐의 top 원소의 x 좌표 + d 가 처음 큐의 top 원소의 y좌표 보다 작다면 쓸모 없으니 버린다.

그게 아닐 경우 이제

두번째 큐의 top원소의 x좌표 + d 보다 처음 큐의 top 원소의 y좌표가 더 크다면 계속해서 두번째 큐의 top 원소를 pop 시킨다. (x좌표 기준 오름차순 큐이므로 x 좌표를 더 크게 늘리는거다!) 

 

그러다 어느 순간 x+d 가 현재 y보다 커진다면 멈추고 처음 큐(현재 좌표)의 top원소를 삽입한다.

매 순간 두번째 큐의 사이즈가 거리 d로 만들 수 있는 철로별 좌표 개수가 된다.

 

어렵다.. 어려워! 큐를 두개 쓴다고 생각하기 어려운 문제 같다.

 

💻 코드

//AC
//BOJ 13334 철로
#include <iostream>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
typedef long long ll;
struct point {
	int x;
	int y;
};
struct compare {
	bool operator()(const point& p1, const point& p2) {
		if(p1.y == p2.y)	return p1.x > p2.x;
		else	return p1.y > p2.y;
	}  // 끝점 기준 정렬
};
struct cmp{
	bool operator()(const point& p1, const point& p2){
		return p1.x > p2.x;
	}
};  // 시작점 기준 정렬
priority_queue<point, vector<point>, compare> pq;  // 끝점 기준 정렬
priority_queue<point, vector<point>, cmp> spq; //시작점 기준 정렬 
int main()
{
	int N;
	vector<point> v;
	cin >> N;
	for(int i=0; i<N; i++){
		int a, b;
		scanf("%d %d", &a, &b);
		v.push_back({a, b});
		if(v[i].x > v[i].y)	swap(v[i].x, v[i].y);
	}
	int d;
	cin >> d;
	for(point tmp: v){
		pq.push(tmp);
	}
	int ans = 0, count = 0;
	while(!pq.empty()){
		if(pq.top().x + d < pq.top().y){   //현재 x-y 거리가 d보다 크면 필요 없음
			pq.pop();
		}
		else{
			while(!spq.empty() && spq.top().x + d < pq.top().y){
				spq.pop();   //현재 y값이 정답큐에 있는 기존 철로 x값+d(거리) 보다 크다면 기존 철로 시작점 x를 버리고 계속해서 증가시킨다.
			}
			spq.push(pq.top()); // 현재 x-y를 정답 큐에 넣는다.
			pq.pop();
			int len = spq.size();   
			ans = max(ans, len);  // 매번 사이즈 비교하여 최댓값 갱신
		}
	}
	printf("%d", ans);
	return 0;
}