[백준] 2141 우체국 - Greedy / Java

• 문제 링크

2141번: 우체국

 

• 풀이 과정

각 마을의 위치 및 인구 수 정보를 입력받으며 total 에 각각의 인구 수를 누적하여 총 인구 수를 구하고,

마을의 정보를 저장한 배열을 위치를 기준으로 정렬한다.

 

각각의 마을의 인구 수를 sum 에 누적하여 해당 값이 총 인구 수의 절반과 같거나 큰 시점이 (sum >= (total + 1) / 2)

해당 위치 기준으로 양 옆의 인구 수가 가장 근접하게 되며,

각 사람들까지의 거리의 합이 최소가 되는 위치이므로 정답으로써 출력한다.

 

• 풀이 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

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

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

        Pair[] arr = new Pair[n];
        long total = 0;
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            long x = Long.parseLong(st.nextToken());
            long a = Long.parseLong(st.nextToken());

            arr[i] = new Pair(x, a);
            total += a;
        }

        Arrays.sort(arr);

        long sum = 0;
        for (Pair p : arr) {
            sum += p.a;
            if (sum >= (total + 1) / 2) {
                bw.write(String.valueOf(p.x));
                break;
            }
        }

        bw.flush();
    }

    private static class Pair implements Comparable<Pair> {
        long x, a;

        public Pair(long x, long a) {
            this.x = x;
            this.a = a;
        }

        @Override
        public int compareTo(Pair o) {
            return (int) (this.x == o.x ? this.a - o.a : this.x - o.x);
        }
    }

}