[백준]2141 - 우체국 (#파이썬 #벡터의 내분, 외분)

 

2141번: 우체국

문제의 조건

첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다. 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다. 범위는 |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다.

N이 10^5으로 O(N^2) 이하의 알고리즘만 적용 가능함을 알 수 있다.

만약 O(N^2) 알고리즘이 적용 가능하다면 모든 N에 대해 우체국을 세워서 해당 우체국에서 마을까지의 거리를 구하면 쉽게 '거리의 합이 최소가 되는 위치'를 찾을 수 있다.

 

문제 접근

임의의 우체국 위치를 가정하고 식을 세워보면 아래와 같은 형태임을 알 수 있다.

 

마을은 (1, 0), (2, 0), (3, 0)에 위치하고, 우체국은(k, 0)에 위치한다고 생각할 수 있다(실제로는 문제 조건에서 수직선이라고 명시했기에 y축에 대한 고려는 필요 없으나 설명의 편의상 y축을 도입함). 우체국이 (k, 0)에 위치할 때 각 마을까지 거리를 계산해보면 아래와 같다.

Latex: $ f(k) = ❘k - 1❘ * 3 + ❘k - 2❘*5 + ❘k - 3❘*3 $

우체국의 위치(k의 값)에 따라 절댓값이 다르게 해석되며 식이 변동하는 것을 알 수 있다. 위 식에서 1, 2, 3은 각각 마을의 위치이다. 즉, 우리는 k 값을 변동해가며 해당 식의 최솟값을 구할 수 있다는 것을 알 수 있다.

 

이 식의 최소값을 구해야한다는 것을 인지한 후에 조금 더 일반화하여 식을 풀어써보면 아래와 같다.

 

k로 나타낸 식이 벡터의 내적, 외적식과 동일하다는 것을 알 수 있다. 즉, x1, x2, x3, x4의 값에 무관하게 a, b, c, d라는 계수의 영향만을 받으며 k가 결정된다!

 

a, b, c, d는 어떻게 k 값에 영향을 줄까? 

• a + b - c - d > 0 이면, 내부에 무게 중심이 존재하는 내분
• a + b - c - d < 0 이면, 외부에 무게 중심이 존재하는 외분

위 사실에 따라 a + b 부분 (여기서는 (a + b)이지만 일반화하여 생각하면 k보다 작은 x의 계수들의 합이다.)이 c + d 보다 크게 되는 순간의 k 값이 정답이 됨을 알 수 있다.

 

코드로 표현하기

위 사실에 따라 'k보다 작은 x의 계수의 합'을 구하면서 해당 값이 나머지 계수의 합(위 식에서 c + d에 해당)보다 커지는 바로 그 시점을 구하면 된다. 왜냐하면 해당 지점이 내분이 되는 가장 왼쪽에 위치한 지점이기 때문이다.

peoples.sort()

acc_cnt = 0
for i in range(N):
    village, people = peoples[i]
    acc_cnt += people
    if acc_cnt >= tot_people / 2:
        print(village)
        break

코드로 표현하면 간단하다.  acc_cnt가 k 보다 작은 x의 계수의 합을 나타내는 역할을 하는 것을 알 수 있다. 그리고 tot_people / 2는 나머지 계수의 합의 역할을 한다. 즉, 나머지 계수의 합보다 크거나 같은 경우의 마을을 출력하면 정답인 것이다.

---

코드는 매우 간단한데 논리를 찾아내는 것이 어려웠다. 특히 x1, x2, x3, ... xi(=우체국과 마을 간 거리)에 무관하게 계수(=마을 사람 수)만 영향을 준다는 사실을 찾아내는 것이 어려웠다. 위 사항을 벡터의 내분, 외분으로 이해한 후에는 쉽게 문제를 해결할 수 있었다.