[PS] 백준 2141 : 우체국(JAVA)

문제

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

2141번: 우체국

---

풀이

그리디 방식을 활용한 풀이

접근법

전처리

입력이 거리순으로 들어오지 않을 수 있으니 거리를 기준으로 정렬

조건

• 각 사람까지의 거리의 합
• 마을이 없는 위치에 우체국을 세울 수 없음
• 마을 위치, 인구 수 입력의 범위는 최대 1,000,000,000
• 마을 거리의 합이 아니라 각 사람까지의 거리의 합이 최소가 되는 위치에 우체국을 세워야 함.

풀이

1. 인구 수 분포의 중간값에 해당하는 위치에 우체국을 세우면 됨.

2. 입력 시 인구 수의 합을 통해 중간값(mid)을 구함.

3. 첫번째 마을부터 탐색 → 인구 수를 증가시키면서 mid값을 넘는 위치를 출력.

---

소스코드

import java.io.*;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

//BOJ_2141 우체국
public class Main {
    static int N, res;
    static int[][] arr;
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

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

        arr = new int[N][2];
        long sum = 0;
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());   //위치
            int a = Integer.parseInt(st.nextToken());   //인구수
            arr[i][0] = x;
            arr[i][1] = a;
            sum += a;
        }

        long middle = (sum+1)/2;

        Arrays.sort(arr, new Comparator<int[]>() {
            public int compare(int[] o1, int[] o2) {
                return o1[0] - o2[0];
            }
        });

        long idx = 0;
        for(int i=0; i<N; i++) {
            idx += arr[i][1];
            if(idx >= middle) {
                res = arr[i][0];
                break;
            }
        }

        System.out.println(res);
    }
}

---

반례

Input
4
3 100
5 30
7 41
10 40

Answer : 5

--------------------------------
Input
3
3 10
1 50
2 41

answer : 2

---

정리

첫 풀이 때 왼쪽 오른쪽의 평균을 구하면 되겠지하고 접근을 했는데 평균을 구하는 과정에서 다양한 실수를 저질러버림..

 

첫번째로 마을의 입력이 순서대로 들어오지 않을 수 도 있다는 점.

두번째로 총합을 미리 구하지 않고 정말 그리디스럽게 0번부터 탐색하며 우체국 자리를 계속 탐색했던 점.

 

결국 미리 총합을 구하고 평균을 구한 후 첫번째 마을부터 탐색을 시작하여 해당 값을 넘는 자리를 탐색하는 방식으로 풀이를 변경하고 시도를 했는데 또 틀리길래 뭐지 했는데,

입력이 1억이 넘는다면 무조건 long을 쓰는 습관이라도 들여야 하나…

 

하여튼 총합을 구하는 과정 및 중앙값 자체가 int형의 최대 범주를 넘어갈 수 있으니 long을 써줘야 한다는 점을 간과함.