[백준 / Java] 2141. 우체국

문제

풀이

1. 입력 받고 정렬하기

N개의 집 위치와 사람 수를 입력 받아 List 자료구조에 저장합니다.

N = Integer.parseInt(br.readLine());
List<int[]> list = new ArrayList<>();

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

  int loc = Integer.parseInt(st.nextToken());
  int people = Integer.parseInt(st.nextToken());
  list.add(new int[] {loc, people});
  slope -= people;
}

집의 위치가 오름차순으로 들어온다는 보장이 없으므로, 집의 위치를 기준으로 리스트를 정렬해줍니다.

list.sort((a, b) -> {
  return a[0] - b[0];
});

2. 언제가 최대일까?

문제의 예제 입력을 기준으로 생각해보겠습니다.

이 상황에서 우체국이 세워지는 위치를 x라고 한다면, "각 사람들까지의 거리의 합"은 아래 식과 같습니다.

그렇다면 이 그래프의 값이 최소가 되는 지점을 찾으면 됩니다.
x에 가능한 모든 수를 대입해보면 되지 않을까 생각해봤지만, 그렇게 하면 시간 초과가 발생할 것입니다.
따라서 직접 대입해보지 않고 더 빠르게 최소값의 위치를 찾는 방법을 생각해야합니다.

위 그래프의 개형은 이렇게 생겼는데요

기울기가 음수에서 양수로 변하는 x=2에서 최소값을 가짐을 확인할 수 있습니다.
기울기의 부호가 변하는 곳에서 최소값을 갖는 이유는, 그 이전까지는 x값이 증가함에 따라 값이 계속 감소하지만, x의 기울기의 부호가 양수로 한번 바뀌고 나면 x값이 증가함에 따라 값이 증가하게 되기 때문입니다.

그럼 입력 값이 이런 경우는 어떨까요?

4
1 3
2 5
10 3
15 5

이런 경우 그래프의 개형은 아래 사진과 같이 나오게 되고, 10~15까지 기울기가 0인 모든 위치에 우체국을 설치해도 최소값이 됩니다.

하지만, 문제 조건에서 최소값이 되는 위치가 여러개인 경우 가장 작은 위치를 출력하라고 했기 때문에 기울기가 음수에서 0으로 바뀌는 지점인 10이 정답입니다.

정리하자면,
기울기가 음수에서 0 이상으로 바뀌는 지점이 최소값이 되는 것입니다.

기울기의 변화 지점을 찾는 것은 간단합니다.

위 식에서 그래프의 기울기에 영향을 주는 것은 앞에 붙은 계수인 사람의 수 밖에 없습니다.
따라서 기울기의 변화는 아래와 같습니다.

(x < 1) : -(3 + 5 + 3)
(1 <= x < 2) : (3) - (5 + 3)
(2 <= x < 3): (3 + 5) - (3) => 기울기의 부호가 바뀌는 부분
(x >= 3) : (3 + 5 + 3)

따라서 초기에 입력 받을때, 초기 slope를 구해주고

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

  int loc = Integer.parseInt(st.nextToken());
  int people = Integer.parseInt(st.nextToken());
  list.add(new int[] {loc, people});
  slope -= people;
}

아래와 같은 방식으로 slope 값을 갱신시켜주고 기울기가 0 이상이 되는 지점의 위치를 저장해서 출력해주면 됩니다.

int ans = 0;
for(int[] cur : list) {
  slope += (cur[1] * 2L);
  if(slope >= 0) {
    ans = cur[0];
    break;
  }
}

전체코드

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

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

    N = Integer.parseInt(br.readLine());
    List<int[]> list = new ArrayList<>();

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

      int loc = Integer.parseInt(st.nextToken());
      int people = Integer.parseInt(st.nextToken());
      list.add(new int[] {loc, people});
      slope -= people;
    }

    list.sort((a, b) -> {
      return a[0] - b[0];
    });

    int ans = 0;
    for(int[] cur : list) {
      slope += (cur[1] * 2L);
      if(slope >= 0) {
        ans = cur[0];
        break;
      }
    }

    System.out.println(ans);
  }
}