백준 2141

●문제 출처

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

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

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

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

●코드

import java.io.*;
import java.util.*;

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		
		int N = Integer.parseInt(br.readLine());
		StringTokenizer st;
		
		node [] arr = new node [N];
		long total = 0;
		
		for(int i = 0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			int village = Integer.parseInt(st.nextToken());
			int human = Integer.parseInt(st.nextToken());
			arr[i] = new node(village,human);
			total += human;
		}
				
		 Arrays.sort(arr, Comparator.comparingLong(o -> o.num));

	     long target = (total + 1) / 2;
	     long prefix = 0;
	     
	     for (node n : arr) {
	            prefix += n.people;
	            if (prefix >= target) {
	                System.out.println(n.num);
	                return;
	            }
	        }
	}
	
	static class node{
		long num;
		long people;
		
		public node(long num, long people) {
			this.num = num;
			this.people = people;
		}
	}
}

●느낀 점

마을 사람 순으로 정렬하여서 처음에 풀었는데, 그게 아니였다....
마을 위치가 작은 순번으로 정렬하고 사람 수 만큼 저장하면서 (total+1)/2 보다 크면 그 값을 출력하면 되는 간단한 문제였다.

N ≤ 100,000
사람 수 ≤ 1,000,000,000

이라 total, target, prefix 이 21억(int 자료형 최대) 가 넘어갈 수 있어서 long 인 것도 주의하면 풀어야겠다.