BOJ - 2141 우체국

leehyunjon·2022년 6월 28일

Algorithm

목록 보기

88/162

Problem

Solve

마을의 위치와 인원수가 최대 10억인것을 보고 이분탐색으로 풀어야겠다고 생각은 했다.
하지만 문제 이해가 잘 안돼서 다른 분의 풀이를 참고했다.

일단 사람까지의 거리의 합이라는 지문이 헷갈렸다.
사람까지의 거리의 합은 사람까지의 거리의 합은 어떤 지점에서 다른 지점까지의 인원의 합이다.
우체국은 각 마을 중 한 곳을 선택할수 있다. 그렇기 때문에 우체국을 중심으로 왼쪽 끝에 있는 마을까지의 인원 합과 오른쪽 끝 마을에 있는 마을까지의 인원 합이 최대한 균형을 맞춰야한다.

예를 들어 X[1] = 1, A[1] = 3, X[2] = 2, A[2] = 5, X[3] = 3, A[3] = 3이라고 할 때, 우체국이 1번 마을에 있다면 왼쪽의 거리합은 1, 오른쪽의 거리합은 8가 된다.
우체국이 2번 마을에 있다면 왼쪽의 거리합은 8, 오른쪽의 거리합은 3이 된다.

이분탐색을 통해 우체국을 임의의 위치에 설치하고 왼쪽의 거리합과 오른쪽의 거리합이 최대한 동일하게 하도록 하되, 같은 값을 가질땐 마을 위치가 가장 가까운 곳을 선정해야한다

풀이 방법은 아래와 같다.

마을 위치를 기준으로 오름차순 정렬한다.
왼쪽마을을 시작으로 각 마을의 인원수의 누적합을 구한다.
이분 탐색을 통해 임의의 우체국 설치 위치를 구한다.
- 우체국 설치 위치를 통해 왼쪽의 거리 합과 오른쪽의 거리합을 구한다.
- 왼쪽의 거리 합 >= 오른쪽의 거리합인 경우, 왼쪽 거리합을 줄이기 위해 end = mid-1을 해준다.
- 이 때 같은 값을 가질때 마을 위치가 가장 작은 곳을 선택해야하기 때문에 >= 조건을 넣어주고 해당 조건에 맞는 최소의 마을 위치를 갱신한다.
- 왼쪽의 거리 합 < 오른쪽의 거리합인 경우, 오른쪽 거리합을 줄이기 위해 start = mid+1을 해준다.

Code

public class 우체국 {
	static int N;
	static int[][] village;
	static long[] sum;
	static int pos;

	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 = new StringTokenizer(br.readLine(), " ");

		N = Integer.parseInt(st.nextToken());

		village = new int[N][2];
		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());
			village[i] = new int[] {x, a};
		}

		//마을 위치 기준 오름차순
		Arrays.sort(village, new Comparator<int[]>() {
			@Override
			public int compare(int[] o1, int[] o2) {
				return o1[0] - o2[0];
			}
		});

		sum[0] = village[0][1];
        //인원의 거리합을 누적합으로 구하기
		for (int i = 1; i < N; i++) {
			sum[i] = sum[i - 1] + village[i][1];
		}

		pos = village[N-1][0];
		binarySearch();

		bw.write(String.valueOf(pos));
		bw.flush();
		bw.close();
	}

	static void binarySearch() {
		int start = 0;
		int end = N - 1;

		while (start <= end) {
			int mid = (start + end) / 2;

			//임의 우체국 위치까지의 왼쪽 거리 합
			long leftSum = sum[mid];
            //임의 우체국 위치부터 오른쪽 끝 마을 까지의 오른쪽 거리 합
			long rightSum = sum[N - 1] - sum[mid];

			//왼쪽 거리 합이 오른쪽 거리 합의 이상이라면 왼쪽 거리합을 줄이기 위해 탐색 범위를 왼쪽으로 줄여준다.
			if(leftSum >= rightSum){
				end = mid-1;
				pos = Math.min(pos, village[mid][0]);
			}
            //오른쪽 거리합이 왼쪽 거리합보다 크다면 오른쪽 거리합을 줄이기 위해 탐색 범위를 오른쪽으로 줄여준다.
            else{
				start = mid+1;
			}
		}
	}
}