7 - 1. 우체국

https://acmicpc.net/problem/2141

2141번: 우체국

 

최근에 푼 그리디 문제 중에, 코테에서도 종종 봤던 유형인 것 같아 이번 기회에 기억에 남길겸 정리해보려 합니다.

문제는 읽기 귀찮으니까 대충 그림으로 표현해서 보겠습니다.

 

아래와 같이 수직선 상 X 좌표에 마을이 존재하고, 각 마을에는 A명의 사람들이 살고 있습니다.

각 사람들의 거리의 합이 최소가 되는 위치에 우체국을 설치하려고 할때 적절한 좌표의 값을 반환하는 문제입니다.

그림 1. 마을 구성

 

위의 예제를 각 좌표별로 계산해보죠.

X 좌표	계산식	거리
0	3 + 10 + 9	22
1	5 + 6	11
2	3 + 3	6
3	5 + 6	11
.....

 

X 좌표가 3을 넘어가면 사람들이 이동해야하는 거리는 점점 멀어지겠죠. 따라서, 답은 2가 됩니다.

이 내용을 어떻게하면 일반화 시킬 수 있을까요.

 

단순하게 생각해볼게요.

임의의 위치에 우체국을 설치하고, 그때 사람들이 이동해야하는 거리를 측정한다 생각해보죠.

그림 2. 우체국 임의의 위치에 설치

그때 이동해야하는 사람의 수가 K라고 합시다.

그리고 해당 위치에서 우체국을 좌/우로 움직일 때, 값이 K - P ~ K + P 사이로 변동되었다고 생각해볼게요.

그림 3. 우체국 위치 변동

그렇다면, 우린 우체국 설치 위치를 왼쪽으로 좀 더 땡겨야 한다는 것을 알 수 있습니다. (오른쪽도 마찬가지겠죠.)

또한, K - P에서 P의 값은 점점 커지다가 어느 순간 다시 증가하리라는 것도 알 수 있습니다. 즉, 이동하는 인원수가 감소하다가 좌측의 극한으로 가다보면, 다시 인원수는 증가할 것이라는 의미죠.

위의 그림을 좌표 평면상에서 표현하면 아래와 같은 그래프를 그릴 수 있습니다.

그림 4. 우체국 위치별 그래프

결국 우리가 구해야하는 값은 언젠가 나타날 min 값이 될겁니다.

그 값을 구하기 전에, 우체국을 수직선 상의 임의의 좌표에 설치할지 아니면 마을에 설치할 것인지 고민해봅시다.

어떤 마을 사이에 우체국을 설치하는 경우와 두 마을 중 하나에 설치하는 경우로 따져보면 될 것 같습니다.

 

그림 5. 우체국 위치 정하기

임의의 좌표 X_c (단, X_b > X_c > X_a)

설치 위치	계산식	설치 결과
마을 A	B * (X_b - X_a) + A * 0	B * X_b - B * X_a
마을 B	A * (X_b - X_a) + B * 0	A * X_b - A * X_a
구간 내 임의의 좌표 C	A * (X_c - X_a) + B * (X_b - X_c)	A * X_c - A * X_a + B * X_b - B * X_c

마을 A와 마을 B에서 연산을 보면 해당 위치에 우체국을 설치하는 경우 그만큼 이동해야하는 인원수가 상쇄됩니다.

디사 말하면 거리가 계속해서 누적되며 인원 수도 증가하니 값이 큰 쪽의 마을에 우체국을 설치하는 것이 최적이라는 것을 어느정도 유추해낼 수 있습니다.

 

 

마지막으로 min 값은 어떻게 구할까요. 그래프를 보면 인원수가 증가하는 양상과 비슷하게 그래프가 그려지고 있습니다. 즉, 누적된 인원수가 절반이상 누적되는 경우 극솟값에 다다르게 될 테니, 그 직후의 마을에 우체국을 설치하는 것이 원하는 답을 도출해낼 수 있겠습니다.

 

우체국 정답 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

/**
 *
 * @author exponential-e
 * 백준 2141번: 우체국
 *
 * @see https://www.acmicpc.net/problem/2141
 *
 */
public class Main {

    private static PriorityQueue<Node<Integer, Long>> villages;

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        villages = new PriorityQueue<>(Comparator.comparingInt(Node::getNode));
        long sum = 0;
        for(int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int X = Integer.parseInt(st.nextToken());
            long A = Long.parseLong(st.nextToken());

            villages.offer(new Node.Builder(X).cost(A).build());
            sum += A;
        }

        System.out.println(postOfficeConstruction(sum));
    }

    /**
     *
     * PostOffice construction
     *
     * line 55: find village that people lives in more than half.
     *
     * @param totalPeople
     * @return
     */
    private static int postOfficeConstruction(long totalPeople) {
        long accumulate = 0L;
        int answer = 0;

        while(!villages.isEmpty()) {
            Node<Integer, Long> current = villages.poll();

            if ((accumulate << 1) < totalPeople) answer = current.getNode();
            accumulate += current.getCost();
        }

        return answer;
    }
}

class Node<T, E> {
    private final T node;
    private final E cost;

    public static class Builder<T, E> {
        //must
        private final T node;
        // opt
        private E cost;

        public Builder(T node) {
            this.node = node;
        }

        public Builder cost(E value) {
            cost = value;
            return this;
        }

        public Node build() {
            return new Node(this);
        }
    }

    private Node(Builder<T, E> builder) {
        node = builder.node;
        cost = builder.cost;
    }

    public T getNode() {
        return node;
    }

    public E getCost() { return cost; }

}