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

백준 2141 - 우체국

시간 제한 2초, 메모리 제한 128MB

# 조건

• 수직선과 같은 일직선상에 N개의 마을이 위치해 있다.
• i번째 마을은 X[i]에 위치해 있으며, A[i]명의 사람이 살고 있다.
• 이 마을들을 위해서 우체국을 하나 세우려고 하는데, 그 위치를 어느 곳으로 할지를 현재 고민 중이다.
• 고민 끝에 나라에서는 각 사람들까지의 거리의 합이 최소가 되는 위치에 우체국을 세우기로 결정하였다.
• 우체국을 세울 위치를 구하는 프로그램을 작성하시오.
• 각 마을까지의 거리의 합이 아니라, 각 사람까지의 거리의 합임에 유의한다

입력

• 첫째 줄에 N(1 ≤ N ≤ 100,000)이 주어진다.
• 다음 N개의 줄에는 X[1], A[1], X[2], A[2], …, X[N], A[N]이 주어진다.
• 범위는 |X[i]| ≤ 1,000,000,000, 1 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다.

출력

• 첫째 줄에 우체국의 위치를 출력한다.
• 가능한 경우가 여러 가지인 경우에는 더 작은 위치를 출력하도록 한다.

# 접근 방법

• 어디서 많이 봤다 했는데 2285번과 거의 같은 문제이다.
  • 2285번과 다른 점은 이 문제는 '가능한 경우가 여러 가지일 경우 빠른 번호의 우체국을 출력'하는 것이다.
• 마을과 해당 마을의 사람 수를 입력받는다.
• 이후에 마을 번호를 기준으로 오름 차순 정렬을 해준다.
• 첫 마을 부터 탐색을 시작하는데
  • 사람들까지의 거리의 합이 최소가 되기 위해서는
  • 현재 마을을 기준으로 왼쪽과 오른쪽의 차이가 최소가 되는 지점에 우체국을 세워야한다.
• 즉, 전체 마을 인구 중 절반을 넘어가는 순간이 그 최소가 되는 지점이다.
  • 따라서 마을 탐색을 시작하기 전 전체 인구 수를 구하고 빼주면서 절반이 넘어가는지 체크한다.
  • 이 때, 1 1, 2 1, 3 1, 4 1 과 같이 들어오는 경우 2번과 3번에서의 거리가 같기 때문에 인구 수의 절반을 구하는 과정에서 // 2 + 1을 해주어야 더 빠른 마을을 찾게 된다.
• 2285번의 경우 누적 합을 이용하여 풀어주었는데 지금보니 sum을 통하여 전체 인구 수를 구하고 빼면서 하는 것이 코드 가독성이 훨씬 좋아 보인다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N = int(input())  
arr = [[*map(int, input().split())] for _ in range(N)]  

arr.sort()  
s = sum(arr[i][1] for i in range(N))  
val = s // 2 + 1  

if N == 1:  
    print(arr[0][0])  
else:  
    for i in range(N):  
        s -= arr[i][1]  
        if s < val:  
            print(arr[i][0])  
            break