[BOJ 23090 // C++] 난민

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

 

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

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

23090번: 난민

 

난민이 어떤 \(x\)좌표에 살더라도 일단 \(x\)축 방향으로 강이 있는 위치인 0으로는 이동해야 함을 관찰하자. \(x\)축 방향 움직임과 \(y\)축 방향 움직임은 독립적이므로 난민이 추가될 때마다 난민들의 \(x\)축 방향으로의 움직인 거리의 총합을 관리해주면 남는 것은 \(y\)축 방향으로의 난민들의 움직이는 거리를 최적화하는 것이다.

 

\(y'\)을 지금까지 추가된 난민들의 \(y\)좌표의 중앙값(median)이라 하자. 이 때 \(y'\) 이하의 \(y\)좌표 중 난민이 있는 좌표의 아래, 혹은 \(y'\) 이상의 \(y\)좌표 중 난민이 있는 좌표의 위에 정수시설을 설치하면 \(y'\)에 설치할 때보다 이동 거리 총합이 항상 늘어남을 어렵지 않게 관찰할 수 있다. 이로부터 매 순간 정수시설을 설치해야 하는 위치를 결정지을 수 있게 된다. 이 위치를 찾는 것은 running median 문제를 푸는 것과 같다.

 

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

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

int N, X;
priority_queue<int> L;
priority_queue<int, vector<int>, greater<>> R;
ll lsum, rsum, xtotal;

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

	L.push(-1000000007), R.push(1000000007);

	cin >> N;
	while (N--) {
		cin >> X;
		xtotal += abs(X);
		cin >> X;
		if (X < R.top()) {
			L.push(X);
			lsum += X;
			if (L.size() == R.size() + 2) {
				lsum -= L.top();
				rsum += L.top();
				R.push(L.top());
				L.pop();
			}
		}
		else {
			R.push(X);
			rsum += X;
			if (R.size() == L.size() + 2) {
				rsum -= R.top();
				lsum += R.top();
				L.push(R.top());
				R.pop(); 
			}
		}

		if (L.size() == R.size()) cout << L.top() << ' ' << xtotal + (ll)L.top() * (L.size() - 1) - lsum + rsum - (ll)L.top() * (R.size() - 1);
		else if (L.size() > R.size()) cout << L.top() << ' ' << xtotal + (ll)L.top() * (L.size() - 1) - lsum + rsum - (ll)L.top() * (R.size() - 1);
		else cout << R.top() << ' ' << xtotal + (ll)R.top() * (L.size() - 1) - lsum + rsum - (ll)R.top() * (R.size() - 1);
		cout << '\n';
	}
}