[백준 2141번] 우체국(파이썬)

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

2141번: 우체국

이 문제는 처음 마주하면

'어라?쉬운데?'하다가

제출하는 순간

???이게 뭐지??

하게 되는 문제.

이 문제에서 대부분의 사람이라면

'각 사람들까지 거리합이 최소'라는 말에 유의합니다.

그래서 최소지점을

'(현재 마을위치-지금 마을위치)x(지금마을 인구)'

이렇게 거리를 구한 뒤

이게 최소가 되는 지점을 찾을 것입니다

 

그런데 이 방식은 시간초과를 만들었습니다.

그래서 처음에 저도 당황했죠.

아니...이게 왜?

그럼 다르게 어떻게?

 

구글링해본 결과

'누적 인구수가 절반을 넘어가는 지점'을 구하면 됩니다.

이유는 가산이 들어가기 때문.

거리를 중심으로 구하지만

인구가 많으면 많을수록 거리값이 가산이 됩니다.

그래서 인구가산이 가장 적은 지역을 구하면 된다

라는 것이 이 문제의 의도같습니다.

#백준 2141번 우체국

N=int(input())
vilage=[[]for _ in range(N)]

po=0
for i in range(N):
    X,A=map(int,input().split())
    vilage[i]=[X,A]
    po+=A
now=0
vilage.sort(key=lambda x:(x[0]))
for i in range(N):
    now+=vilage[i][1]
    if now>=po/2:
        print(vilage[i][0])
        break

 

그리디 문제에서 좀 독특한 편에 속합니다.

이전에 풀때는 풀이를 보고도

뭔소리인지 이해를 못해서 헤맬 정도.

이런 류의 문제가 있구나 정리하고 넘어가시는 것도 좋아보이네요.