이번 문제는 백준의 골드 4 우체국 문제이다.
문제를 한 번 차근차근 읽어보도록 하자.
일직선 상에 N개의 마을과 A[i]명의 사람이 주어지며,
최대 100000개의 마을, 10억의 위치, 10억의 사람이 입력으로 주어진다.
모든 사람에 대해 최소 거리가 되도록 우체국을 설치해달라고 한다.
우선, 문제의 입력으로 주어지는 값이 굉장히 크다.
또한, 마을로 주어지는 케이스도 10만개로 굉장히 많다.
따라서 완전 탐색을 통해 설치하기엔 매우 부적합 해보인다.
문제를 다시 한 번 읽어보면, 모든 사람으로부터의 거리 임을 강조한다.
그 말은, 마을의 위치가 주어졌을 때 인구 수에 따라 가중치를 줘야한다는 말이다.
사람이 적을 수록 가중치는 줄며, 사람이 많을 수록 해당 마을에 가까워 질 것이다.
또한, 모든 사람에 대해 최소 거리가 되려면 가운데에 가까울 수록 유리함을
우리는 직관적으로 알 수 있다.
그럼 최대한 가운데에 위치한 마을을 어떻게 찾을 수 있을까?
단순 계산
사실 단순 계산을 통해서 계산을 할 수 있다고 생각한다.
인구 수에 따라 가중치를 곱하고, 인구 수로 나눈 평균을 구하면?
정가운데 위치의 값이 나올 것이다.
해당 값은 소수로 나올 수도 있는데, 반올림 하면 될 것 같다.
시간 초과가 발생하거나 수의 범위에 의해 연산 오류가 나지 않을까?
우선 한 번 구현해보자.
int main() {
cin >> num;
for (int i = 0; i < num; i++) {
cin >> village >> population;
sum += (village * population);
pop_sum += population;
}
avg = sum / pop_sum;
cout << round(avg);
return 0;
}역시 통과를 하지 못한 풀이였다.
문제는 Tie break 조건을 처리할 수 없다는 점이었다.
이분 탐색
위의 풀이는 사실 조금 될 지 안될 지 의심하며 구현했었다.
문제에 굳이 Tie break 조건이 걸려있는 것도 그렇고
단순 계산으로 풀어야 할 문제는 아니라는 생각이 들었다.
그래서 어떻게 빠르게 계산할까 생각하다보니, 이분 탐색이 떠올랐다.
정확히는 Parametric search 방식이 떠올랐다.
가운데 값을 넘겨 위치를 조정해가며 최적의 위치를 찾는 것이다.
이제 어떤 조건에, 가운데 값을 어떻게 처리할 지가 관건이다.
우선, 마을을 번호 순서대로 오름차순 정렬을 하는 게 좋을 것 같다.
그래야 앞에서부터 연산을 진행하며 가운데를 찾기가 수월할 것이다.
조건 설정
그럼 이제 문제는 가운데 값을 옮길 조건이다.
대충 마을들의 가운데를 먼저 짚은 다음 어떤 연산을 진행하고,
해당 연산의 결과에 따라 가운데 값을 옮겨야 할 것이다.
만약 가운데를 기준으로 왼쪽 오른쪽의 합을 비교한다면 어떨까?
왼쪽의 인구 합과 오른쪽의 인구 합 비중에 따라 가운데 값을 옮긴다면?
왼쪽의 인구가 더 많으면 가운데 값을 더 왼쪽으로 옮겨야 할 것이다.
즉, 가운데 값의 왼쪽을 새로운 오른쪽 끝 값으로 설정하는 것이다.
여기서 한 가지 더 생각해야 할 부분이 생긴다.
그럼 중간 값이 바뀔때마다 매번 합을 구해서 비교해야 할까?
10만개의 마을이 있으면 시간초과가 발생할 수도 있을 것이다.
따라서 누적 합 개념을 이용해 합을 미리 계산하도록 한다.
이제 조건까지 생각했으니, 구현만 하면 된다.
구현 코드는 아래와 같다.
for (int i = 0; i < num; i++) {
cin >> village >> population;
villages.push_back({ village, population });
// 마을을 순서대로 정렬하기 위해 village를 앞으로 둔다.
}
sort(villages.begin(), villages.end());
// 마을을 위치 순서대로 오름차순 정렬
piled_sum.push_back(villages[0].second);
for (int i = 1; i < num; i++)
piled_sum.push_back(piled_sum[i-1] + villages[i].second);
ll left = 0, right = num - 1;
while (left <= right) {
ll mid = (left + right) / 2;
// 어떤 기준으로 mid를 옮길 것인가?
ll partial_left_sum = piled_sum[mid];
ll partial_right_sum = piled_sum[num - 1] - piled_sum[mid];
if (partial_left_sum >= partial_right_sum) {
right = mid - 1;
answer = min(answer, villages[mid].first);
}
else
left = mid + 1;
}