For a better world

문제에서 요구하는 핵심은 어떤 한 마을에 우체국이 세워진다 가정할 때, 다른 마을 사람들이 우체국이 세워진 마을에 가기 위해 필요한 거리의 합이 최소가 되는 마을 번호를 찾는 것이다. 크게 두 가지 아이디어가 있다. 첫 번째는 단순하게 모든 마을 사람의 총합을 구하고 [(마을 번호, 사람 수), (마을 번호, 사람 수), ...]의 리스트를 순회할 때 절반이 넘어가는 그 마을 번호를 찾는 것이다. 이 접근이 정답의 핵심 아이디어다. 처음에 이 방법이 희번뜩하며 떠올랐지만 단순하단 이유로 올바른 접근이 아닐 것이란 생각을 하고 다른 방법을 찾게 됐다. 

[정답 코드]

import sys
input = sys.stdin.readline

villiage = []
all_people = 0

N = int(input())

for i in range(N):
    n_viliage, people = map(int, input().split())
    villiage.append([n_viliage, people])
    all_people += people

villiage.sort(key= lambda x: x[0])

count = 0
for i in range(N):
    count += villiage[i] [1]
    if count >= all_people/2:
        print (villiage[i][0])
        break

두 번째 아이디어는, 반복문을 통해 [(마을 번호, 사람 수), (마을 번호, 사람 수), ...]을 차례대로 돌면서 최소 값을 구하는 것이다. 구체적으로 첫 번째 마을에 우체국이 세워졌다 가정하면 두 번째 세 번째 마을에서 사람들이 오기 위해 얼마나 비용이 드는지를 구하는 것이다. 예제 입력을 예시로 삼는다면

첫 번째 루프 즉, 첫 번째 마을에 우체국이 세워진다면 아래와 같이 총 11의 비용이 든다.

(1번째 마을 - 1) * 3 = (1-1) * 3 = 0

(2번째 마을 - 1) * 5 = (2-1) * 5 = 5

(3번째 마을 - 1) * 3 = (3-1) * 3 = 6

두 번째 루프 즉, 두 번째 마을에 우체국이 세워진다면 아래와 같이 총 6의 비용이 든다.

(1번째 마을 - 2) * 3 = (1-2) * 3 = 3 

(2번째 마을 - 2) * 5 = (2-2) * 5 = 0

(3번째 마을 - 2) * 3 = (3-2) * 3 = 3

세 번째 루프 즉, 세 번째 마을에 우체국이 세워진다면 아래와 같이 총 11의 비용이 든다.

(1번째 마을 - 3) * 3 = (1-3) * 3 = 6

(2번째 마을 - 3) * 5 = (2-3) * 5 = 5

(3번째 마을 - 3) * 3 = (3-3) * 3 = 0

* 음수가 되는 부분은 절대값을 취해줘야 함

따라서 총 6의 비용이 드는 두 번째 마을이 가장 우체국을 세우기 적합한 것이다. 이를 구현한 코드는 아래와 같으며, O(N^2)의 시간 복잡도로 인해 시간 초과가 발생한다.

[초기 시도한 코드]

import sys
input = sys.stdin.readline

N = int(input())

village = [0] * (N + 1)
people = [0] * (N + 1)

min_values = [0] * (N +1)

for i in range(1, N+1):
    x, a = map(int, input().split())
    village[i] = x
    people[i] = a

for i in range(1, N+1):
    value = 0
    for j in range(1, N+1):
        value += abs(village[j] - i) * people[j]
    
    min_values[i] = value

del min_values[0]
index = min_values.index(min(min_values))
print (village[index+1])