[백준 - 2141][GOLD 4][해설 X] - 우체국 (JAVA)

문제 링크

---

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 이며 모든 입력은 정수이다.

 

출력

---

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

 

해결 코드

---

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

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

        int N = Integer.parseInt(br.readLine());

        Village[] villeges = new Village[N];

        long total = 0;

        for(int i=0;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            villeges[i] = new Village(i+1,Integer.parseInt(st.nextToken()),Integer.parseInt(st.nextToken()));

            total += villeges[i].count;
        }

        //거리순으로 정렬
        Arrays.sort(villeges,(a,b)->(a.location - b.location));

        long count = 0;
        long mid = (total+1)/2;


        //왼쪽 마을의 인구수가 오른쪽 마을의 인구수보다 크거나 같을 경우가 거리 합의 최소이다.
        //왜냐하면 왼쪽 마을과 오른쪽 마을간의 거리 합이 최소이기 위해선 모든 인구의 중앙값에 세워야 되기 때문이다.
        for(int i=0;i<villeges.length;i++){
            count += villeges[i].count;

            if(count >= mid){
                System.out.println(villeges[i].location);
                break;
            }
        }
    }
}
class Village{
    int seq;
    int location;
    int count;

    public Village(int seq, int location, int count){
        this.seq = seq;
        this.location = location;
        this.count = count;
    }
}

 

 

실행 결과

---

 

팁

---

• 모든 사람과의 거리가 최소이려면 모든 사람의 중앙값에 배치해야 한다.