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

2141번: 우체국

 

코드

import sys
import math
n = int(input())
n_list = []
for _ in range(n):
    a,b = map(int,sys.stdin.readline().split())
    n_list.append([a,b])

n_list.sort()
cnt = 0
total = 0
for i in range(n):
    total += n_list[i][1]

for a,b in n_list:
    cnt+=b
    if cnt >= math.ceil(total/2):
        print(a)
        break

 

설명

전체 인구의 절반 이상을 차지하는 마을에 설치하는 것이 가장 효율적이라고 한다..

마을 순서대로 오름차순 정렬을 하고 총 인구 수를 미리 구해놨다.

리스트에 넣어놓은 인구 수를 cnt에 차례대로 더하면서 총 인구수를 2로 나눈 값에 올림한 값과 비교하여 크거나 같으면 해당 마을 번호를 출력해줬다.