[백준] 2141번: 우체국(Python)

문제 링크

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

2141번: 우체국

 

풀이 

풀이 설명

- 분류 : 그리디 & 누적합

처음엔 '공유기 설치(이진탐색)'문제와 비슷해서 이건 '거리', '사람 수' 둘다 고려해야하는 이진탐색인가? 로 시작했지만, 

결국 거리는 정렬 말고는 필요없는 문제였다.

처음엔 이해가 안돼서 여러 풀이를 봤는데 다들 사람의 총합/2를 넘는 부분에 놓으면 된다고만 하지 이유가 자세히 안써져있었다. 

내가 바보라서 그래.. ^,, 

-> 이해한 풀이를 써보자면

• 중앙값처럼 사람을 기준으로 사람이 많은 곳에 놓는 것이 최선이다. 
• 그러므로 총 사람의 수에서 왼쪽과 오른쪽의 수가 같을 때 그 지점에 놓는 것이 중앙값처럼 결정되는 것이다.
• 왼쪽부분 L 오른쪽 부분 R로 칭하면 L >= R 이 되는 순간의 지점에 설치하는 것
• 이 지점을 찾기 위해 누적합을 이용하면 빠르게 찾을 수 있다. (거리, 사람 수 값이 10억이므로^..)
• 백준 꿀따기(링크) 랑 비슷한 문제!

풀이 코드

import sys
input = sys.stdin.readline

n = int(input())
info = []
for _ in range(n):
    info.append(tuple(map(int, input().split())))

info.sort()

# L>R 인 순간에 놓으면 되니까 절반을 넘는 곳에 놓으면 된다.
prefix = [0] * n
prefix[0] = info[0][1]

for i in range(1, n):
    prefix[i] = prefix[i-1] + info[i][1]

for i in range(n):
    left = prefix[i]
    right = prefix[n-1] - prefix[i]
    if left >= right:
        print(info[i][0])
        break