[PS] BOJ 2141 / 우체국

문제 링크: https://www.acmicpc.net/problem/2141

풀이

예제 입력을 보며 풀이를 찾아봅시다.

# 예제 데이터
3
1 3
2 5
3 3

먼저, 각 마을의 인구 수가 동일하다고 가정해 단순화한 문제를 풀어 봅시다. 이 경우, [1, 2, 3]에서 중간 값을 찾으면 되는 문제가 되고 답은 2임을 알 수 있습니다.

이제, 각 마을의 인구 수를 배열에 반영해 봅시다. 이 경우, 전체 배열은 [1, 1, 1, 2, 2, 2, 2, 2, 3, 3, 3]이 됩니다. 중간 값을 찾아보면 2임을 알 수 있습니다.

하지만, $N$은 최대 10⁵이며, 각 마을의 인구 수는 최대 10⁹입니다. 위의 방법대로 배열에 인구 수를 반영하기엔 메모리 제한을 초과합니다. 대신에, 길이 $N$의 배열을 좌표를 기준으로 오름차순 정렬한 뒤, 앞에서부터 인구의 합을 계산하며 인구의 수가 절반에 도달하는 지점을 찾으면 됩니다.

전체 코드

input = open(0).readline

N = int(input())
arr = [None] * N
total = 0 # 전체 인구만 별도로 합산
for i in range(N):
    arr[i] = tuple(map(int, input().split()))
    total += arr[i][1]

arr.sort(key=lambda e: e[0]) # 좌표를 기준으로 오름차순 정렬

half_people = (total + 1) // 2 # 홀/짝 모두 상관없이 절반 이상이 되는 지점을 찾기 위함
lsum = 0
for i in range(N):
    lsum += arr[i][1]
    if lsum >= half_people:
        print(arr[i][0])
        break