백준 2141

2141번: 우체국

---

문제

수직선과 같은 일직선상에 N개의 마을이 위치해 있다. i번째 마을은 X[i]에 위치해 있으며, A[i]명의 사람이 살고 있다.

이 마을들을 위해서 우체국을 하나 세우려고 하는데, 그 위치를 어느 곳으로 할지를 현재 고민 중이다. 고민 끝에 나라에서는 각 사람들까지의 거리의 합이 최소가 되는 위치에 우체국을 세우기로 결정하였다. 우체국을 세울 위치를 구하는 프로그램을 작성하시오.

각 마을까지의 거리의 합이 아니라, 각 사람까지의 거리의 합임에 유의한다

입력

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다.

 

출력

첫째 줄에 우체국의 위치를 출력한다. 가능한 경우가 여러 가지인 경우에는 더 작은 위치를 출력하도록 한다.

 

제한

• 시간 제한 : 2초
• 메모리 제한 : 128MB

---

문제 풀이 과정

각 사람들의 거리의 합이 최소가 되려면, 해당 마을을 기준으로 왼쪽, 오른쪽의 사람 수가 균일해야 한다.

즉, 총 인구수의 중간값에 가장 가까운 마을에 우체국이 설치되어야 한다.

처음으로 중간값 보다 크거나 같은 곳을 찾을 경우 그곳이 우체국을 설치할 자리이다.

---

정답 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

class Main2141 {

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

		int N = Integer.parseInt(br.readLine());
		PriorityQueue<Pair> pq = new PriorityQueue<>();
		long peopleSum = 0;
		long answer = 0;
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine());
			int idx = Integer.parseInt(st.nextToken());
			int people = Integer.parseInt(st.nextToken());
			pq.add(new Pair(idx, people));
			peopleSum += people;
		}

		long tmp = 0;
		for (int i = 0; i < N; i++) { //제일 왼쪽 마을 부터 탐색
			Pair p = pq.poll();
			tmp += p.people;
			if ((peopleSum + 1) / 2 <= tmp) { //우체국을 세울때 (왼쪽 부분 + 오른쪽 부분)/2 보다 왼쪽 까지 센 부분이 크면 그곳이 우체국을 세울 자리
				answer = p.idx;
				break;
			}
		}

		System.out.println(answer);
	}

	private static class Pair implements Comparable<Pair> {
		int idx, people;

		public Pair(int idx, int people) {
			this.idx = idx;
			this.people = people;
		}

		@Override
		public int compareTo(Pair o) {
			return this.idx - o.idx;
		}
	}
}