BOJ 2141 우체국

https://www.acmicpc.net/problem/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 이며 모든 입력은 정수이다.

---

출력

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

---

예제 입력 1

3
1 3
2 5
3 3

예제 출력 1

2

---

코드

각 사람까지의 거리의 합이 최소가 되기 위해서는 전체 인구의 절반이 처음 넘게 되는 마을에 우체국을 세우면 된다.

예제 1을 예로 들어보면 다음과 같다.

• 전체 인구: 11명
• 절반 인구: 6명 (올림)

1. 첫 번째 마을까지의 인구: 3명
2. 두 번째 마을까지의 인구: 8명

처음으로 절반의 인구를 넘는 마을은 두 번째 마을이므로, 정답은 두 번째 마을의 위치 즉, 2가 된다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

    static class Town {
        int position;
        int population;

        public Town(int position, int population) {
            this.position = position;
            this.population = population;
        }
    }

    static long halfPopulation = 0;
    static Town[] towns;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        towns = new Town[N];
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int position = Integer.parseInt(st.nextToken());
            int population = Integer.parseInt(st.nextToken());
            towns[i] = new Town(position, population);
            halfPopulation += population;
        }
        halfPopulation = (long) Math.ceil(halfPopulation / 2.0);

        Arrays.sort(towns, Comparator.comparingInt(town -> town.position));

        int answer = findPosition();
        System.out.println(answer);
    }

    static int findPosition() {
        int halfPosition = 0;
        long countPopulation = 0;
        for (Town town: towns) {
            countPopulation += town.population;

            if(countPopulation >= halfPopulation) {
                halfPosition = town.position;
                break;
            }
        }

        return halfPosition;
    }
}