https://www.acmicpc.net/problem/2285
▲ 문제 바로가기

수직선상에 마을이 분포해 있고, 각 마을에는 사람들이 살고 있다. 그리고 각 사람들까지의 거리의 합이 최소가 되는 위치에 우체국을 세우는 문제이다.

Approach 1: Naive

가장 쉽게 생각할 수 있는 방법은 범위 내의 모든 점에 대해 각 사람들까지의 거리의 합을 직접 구하는 것이다. 하지만 범위의 길이가 최대 20억, 사람 수는 10억이기 때문에 엄청나게 큰 수가 나오고, 오버플로우가 발생한다.

좌표의 모든 점이 아닌, 입력으로 들어온 최대 10만 개의 마을에 우체국을 세운다고 해도 여전히 $20억 * 10억 * 10만$을 계산해야 한다. long long 타입을 사용해도 담을 수 없는 큰 수이다.

Approach 2: 가중 평균

그 다음으로 생각한 방법은 가중평균을 구하는 것이다. 입력으로 들어온 마을 좌표와 사람 수를 곱해서 더한 뒤, 총 사람 수로 나눈다. 하지만 이 방법도 수식을 활용하는 것 뿐, $10억 * 10억 * 10만$을 계산해야 하기 때문에 구할 수 없다.

사실 가중평균은 거리의 제곱의 합을 최소화하기 때문에, 절댓값 거리의 합을 최소화해야 하는 이 문제에서는 잘못된 사용이다.

Approach 3: 그리디

불현듯 이전에 어디선가 봤던 방법이 떠올랐다. 마을까지의 거리의 합이 아닌 각 사람들까지의 거리의 합을 최소화해야 한다. 우체국을 기준으로 왼쪽에 사는 사람들의 합과 오른쪽에 사는 사람들의 합이 같다면 되지 않을까?로 접근했다.

위와 같은 상황을 생각해보았다. -99~99 사이 어느 곳에 우체국이 있어도 거리의 합은 200으로 같다. 이보다 더 작을 수는 없다.

그렇다면 사람이 조금 더 분포해 있어도 이 추측이 들어 맞을까?

위와 같은 경우에도 들어 맞는 것을 확인할 수 있었다.

하지만 이 문제의 예제를 보면, 좌우에 사는 사람의 수가 같아지는 점이 마을이 있는 좌표라는 것을 알 수 있다.

우체국이 2에 있다고 가정했을 때 좌우에 3명씩 있기 때문에 우체국이 2에 있으면 된다. 하지만 입력으로 주어지는 분포가 대칭형이라는 보장은 없다.

언제 최소가 될까?

우체국을 기준으로 좌우에 사는 사람의 수가 같으면 최소가 된다는 것을 몇 가지 예제를 통해 확인했다. 하지만 이것은 특수한 경우고, 최소를 만들기 위해서는 우체국 기준 좌우에 사는 사람의 수를 최대한 비슷하게 우체국의 위치를 잡아야 한다.

그리고 우체국이 세워진 곳에 사람이 많이 살고 있으면 유리하다. 그 사람들은 우체국까지의 거리가 0이 되기 때문이다.

구현

1. 먼저 입력으로 들어온 모든 사람의 수의 합을 구한다.
2. 입력을 좌표 순으로 오름차순 정렬한다. 문제의 조건에서 거리의 합이 최소가 되는 점이 여러 개일 경우 그 중 작은 값을 출력해야 하기 때문이다.
3. 배열을 순회하면서 사람 수의 누적 합을 계산한다. 만약 그 값이 전체 사람 수의 절반 이상이라면 그때의 좌표를 출력하고 순회를 멈춘다.

위 그림처럼 직접 계산해 보면서 관찰한 내용을 토대로 코드를 작성했고, 정답 처리되었다.

문제는 풀었지만 개운한 느낌이 들지 않았다. 왜 우체국이 사람 수의 절반쯤 되는 지점에 있으면 거리의 합이 최소가 되는 걸까? 수식으로 좀 더 명확히 이해하고 싶었다.

수식으로 이해하기

수식 정의

거리의 합을 다음과 같이 정의할 수 있다.

문제의 목표는 $D(x_k)$를 최소화하는 것이고, 그러기 위해서는 $x_k$에 따라 변하는 $D(x_k)$의 변화량을 관찰해보자.

변화량 관찰

먼저 위 수식에서 절댓값을 풀어보자.

$D(x_k)$의 변화량인 $\Delta D(x_k)$는 다음과 같다.

절댓값을 푼 수식에서 $x_k$가 커짐에 따라 증가하는 부분은 +의 부호만 가지게 되고, 감소하는 부분은 -의 부호만 가지게 된다.

변화량의 각 항을 이해해보자!
첫 번째 항은 우체국보다 왼쪽에 있는 사람 수의 합이다. 두 번째 항은 우체국보다 오른쪽에 있는 사람 수의 합이다. 그 두 항의 차가 곧 변화량이다.

$x_k$는 가장 작은 값(입력 중 가장 작은 좌표)에서부터 점점 커진다. 처음에는 변화량도 가장 작은 값을 갖는다. 그때 두 번째 항의 값이 가장 크기 때문이다.

$x_k$가 커지면서 변화량도 함께 증가하고, 그러다가 어느 순간 변화량이 0 이상이 되는 순간이 생긴다. 그 때 거리의 합은 최소가 된다.

$i$는 정수이기 때문에 위에서 정의한 거리의 합과 변화량 모두 실수에서 연속인 함수가 아니다. 따라서 변화량이 정확히 0이 되는 점이 없을 수 있기 때문에 처음으로 0 이상인 점을 찾아야 한다.

결론

변화량이 처음으로 0 이상이 되는 점, 왼쪽 사람 수가 오른쪽 사람 수보다 같거나 많아지는 순간을 찾아야 한다는 것을 수식을 통해 이해할 수 있다.

마무리

이러면 되지 않을까? 감으로 해결한 문제여서 풀고 나서도 찝찝함이 남아있었다. 하지만 수식을 통해 실제로도 그럴 수밖에 없다는 것을 증명해 내니 남아있던 찝찝함이 해소되었다.

입력으로 분포가 주어지고, 그 중 하나의 점을 잡았을 때 거리의 합이 최소가 되는 점을 찾는 유형. 꽤 많이 보이는 것 같다. 증명을 했으니 앞으로 비슷한 상황이 왔을 때 이 테크닉을 생각해낼 수 있도록 연습해야겠다.😊

틀린 부분이 있다면 언제든 피드백 남겨주세요 :)