[Java] 백준 2141번 우체국

그리디, 이분탐색으로 문제를 해결할 수 있습니다.

각 마을 중에 한곳에 우체국을 세울 때 각 사람들과 우체국의 거리의 합을 가장 적게 할 수 있는 위치를 찾아야 합니다.

1. 마을 인덱스를 기준으로 정렬합니다.
2. 누적합을 통해서 마을 사람들 수를 구해줍니다.
3. 이분탐색을 통해서 해당하는 위치까지의 사람들 수와 이후의 사람들 수를 비교합니다.
4-1. 해당 위치까지의 사람들 수가 더 많을 때 현재위치를 right로 변경하고 3번을 진행합니다.
4-2. 해당 위치까지의 사람들 수가 더 적을 때 현재위치를 left로 변경하고 3번을 진행합니다.

위의 과정을 통해서 최적의 위치를 찾고 출력해줍니다.

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

public class Main {
  public static void main(String[] args) throws Exception {
    BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
    StringTokenizer st = null;

    int n = Integer.parseInt(br.readLine());
    ArrayList<Pair> al = new ArrayList<>();
    long[] sum = new long[n];

    for (int i = 0; i < n; ++i) {
      st = new StringTokenizer(br.readLine());
      int x = Integer.parseInt(st.nextToken());
      int a = Integer.parseInt(st.nextToken());

      al.add(new Pair(x, a));
    }

    Collections.sort(al, (Pair a1, Pair a2) -> {
      return a1.loc - a2.loc;
    });

    sum[0] = al.get(0).num;
    for (int i = 1; i < n; ++i) {
      sum[i] = sum[i - 1] + al.get(i).num;
    }

    int left = 0;
    int right = n - 1;
    long dist = Long.MAX_VALUE;
    while (left <= right) {
      int mid = (left + right) / 2;

      if (sum[mid] >= sum[n - 1] - sum[mid]) {
        right = mid - 1;
        dist = Math.min(dist, al.get(mid).loc);
      } else {
        left = mid + 1;
      }
    }

    bw.write(dist + "\n");
    bw.close();
  }

  public static class Pair {
    int loc;
    int num;

    public Pair(int loc, int num) {
      this.loc = loc;
      this.num = num;
    }
  }
}