취미로 코딩하기

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

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

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

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

$y^{\prime }$을 지금까지 추가된 난민들의 $y$좌표의 중앙값(median)이라 하자. 이 때 $y^{\prime }$ 이하의 $y$좌표 중 난민이 있는 좌표의 아래, 혹은 $y^{\prime }$ 이상의 $y$좌표 중 난민이 있는 좌표의 위에 정수시설을 설치하면 $y^{\prime }$에 설치할 때보다 이동 거리 총합이 항상 늘어남을 어렵지 않게 관찰할 수 있다. 이로부터 매 순간 정수시설을 설치해야 하는 위치를 결정지을 수 있게 된다. 이 위치를 찾는 것은 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';
	}
}