[Python] 백준 2141번: 우체국

https://www.acmicpc.net/problem/2141

2141번: 우체국

import sys
input = sys.stdin.readline


N = int(input())
postOffice = [list(map(int, input().split())) for _ in range(N)]

postOffice.sort(key=lambda x: x[0])
mid = round(sum(p for _, p in postOffice)/2)

pCount = 0
for i, p in postOffice:
    pCount += p

    if pCount >= mid:
        print(i)
        break

for문으로 위치를 기준으로 정렬된 마을들을 돌면서 pCount를 해당 마을의 p값을 더해간다. 특정 마을에서 pCount를 갱신했을 때, 전체 인구수의 절반을 넘기게 된다면 해당 마을에 우체국을 세우면 된다.

 

여담으로 해당 문제를 스스로 푸는 것에 실패하였다. 그리디는 '이렇게 하면 되지 않을까?'라는 직관으로 아이디어를 얻어야 하는 듯하다. 필자는 '해당 지점에서의 인구 수가 절반을 넘길 경우'라는 발상을 정말 생각조차 못하였다. 글들을 뒤져봐도 정확한 수학적 원리에 대한 설명을 찾아볼 수 없었다.

스스로 한 문제 분석으로 얻은 힌트로는

1. 인구와 거리를 고려한 이동 거리가 V자 형태의 일부이며, 꼭지점이 우체국의 건설 지점이 된다.

2. 우체국은 마을 밖에 지어선 안 된다.

이 정도가 끝이었는데, 복잡할 것으로 예상되는 문제가 누적합만으로 풀 수 있다는 사실까지 어떤 과정을 거쳐 도달하였는지 정말 궁금하다.

정말 골드 4 문제인지 의문이다.