[백준] 2141번 우체국 ★★★

💡문제접근

• 문제 그대로를 푸는 과정에서 이중 for문에 의한 시간복잡도인 O(N^2)때문인지 시간초과가 나왔고 계속 풀어도 도저히 답을 찾지 못해 구글링을 했는데 쉽사리 이해가 가지 않았다.
• 누적 인구수의 절반을 넘어서는 시점에 마을에 우체국을 설치해야한다.는 이 조건을 문제에서 어떻게 도출할 수 있는 것인지 아직도 의문이다.

💡코드(메모리 : 46764KB, 시간 : 292ms)

import sys
input = sys.stdin.readline

N = int(input())
post = []
total = 0
for _ in range(N):
    X, A = map(int, input().strip().split())
    post.append([X, A])
    total += A

post.sort()
tmp = 0
for i in range(N):
    tmp += post[i][1]
    if tmp >= total / 2:
        print(post[i][0])
        break

💡소요시간 : 1h