[BOJ 18266 // C++] Meetings

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 18266번 문제인 Meetings이다.
문제는 아래 링크를 확인하자.

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

18266번: Meetings

소들의 번호를 생각하지 않고 시간의 흐름에 따른 소의 위치가 어떻게 되는지만을 생각하면 소들의 움직임은 각 소가 처음 보고 있는 방향으로 (다른 소와의 만남에 상관없이) 계속 직진하는 모습과 같다는 점을 관찰하자. 잘 이해가 안된다면 두 소가 만나서 서로 뒤돌아 움직이는 모습과 두 소가 만나고 그대로 지나가는 모습은 번호를 떼고 보면 똑같아보이는 점을 생각해보자.

 

위의 관찰을 이용하면 왼쪽 헛간과 오른쪽 헛간에 (몇번 소인지는 몰라도) 각각 소가 들어오는 시각이 언제일지를 빠르게 구해낼 수 있다.

 

한편, 두 헛간 사이에 있는 소들 중 소 하나가 다음으로 헛간에 들어간다면 그 소는 맨 왼쪽의 소 또는 맨 오른쪽의 소가 될 수밖에 없음을 관찰하자. 중간에 있는 소가 순서를 바꿔 헛간으로 들어갈 수는 없기 때문이다. 이와 먼젓번에서 구한 각 헛간에 소가 들어오는 시각을 이용하면 소들이 헛간에 들어가는 순서를 시간순으로 알 수 있다. 이를 이용해 T값을 구해내자.

 

한편, 좌표 x, y에 있는 두 소가 시간 T 이하에 만난다는 것은 x<y이며 x에 있는 소는 오른쪽을 보고 y에 있는 소는 왼쪽을 바라보고 x+T >= y-T를 만족한다는 것과 같다. 이러한 관계를 만족하는 쌍의 수는 각 소들을 좌표 오름차순으로 살펴보면서 오른쪽을 살펴보고 있는 소들이 들어있는 monotone queue를 관리하는 것으로 빠르게 구해낼 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
#include <algorithm>
#include <queue>
using namespace std;
typedef long long ll;

int N; ll L, T;
int arr[50000];
int wgt[50000], total;
ll pos[50000];
int dir[50000];
queue<int> dirque;
ll dist[50000];
int psum, lll, rrr;

ll ans;

bool compD(int& x1, int& x2) {
	return dist[x1] < dist[x2];
}

bool compP(int& x1, int& x2) {
	return pos[x1] < pos[x2];
}

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

	cin >> N >> L;

	for (int i = 0; i < N; i++) {
		arr[i] = i;
		cin >> wgt[i] >> pos[i] >> dir[i];
		total += wgt[i];
		if (dir[i] > 0) dist[i] = L - pos[i];
		else dist[i] = pos[i];
	}
	total = (total + 1) / 2;
	
	sort(arr, arr + N, compD);

	for (int i = 0; i < N; i++) {
		int& idx = arr[i];
		dirque.push(dir[idx]);
	}

	sort(arr, arr + N, compP);

	lll = 0, rrr = N - 1;
	while (psum < total) {
		if (dirque.front() < 0) {
			int& idx = arr[lll];
			psum += wgt[idx];
			lll++;
		}
		else {
			int& idx = arr[rrr];
			psum += wgt[idx];
			rrr--;
		}
		dirque.pop();
	}

	sort(arr, arr + N, compD);

	T = dist[arr[lll + (N - 1 - rrr) - 1]] * 2;

	sort(arr, arr + N, compP);

	queue<ll> que;
	for (int i = 0; i < N; i++) {
		int& idx = arr[i];
		if (dir[idx] > 0) que.push(pos[idx]);
		else {
			while ((!que.empty()) && que.front() + T < pos[idx]) que.pop();
			ans += que.size();
		}
	}

	cout << ans;
}