백준2141(우체국) - 해결

우체국

 

문제

수직선과 같은 일직선상에 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, 0 ≤ A[i] ≤ 1,000,000,000 이며 모든 입력은 정수이다.

 

출력

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

---

처음에는 이분 탐색으로 풀까하였지만 비교 방법이나 줄이거나 늘리는 방식을 생각하다가 생각한 것이

총 길이를 구하고 길이의 변화를 보는 방식으로 구하였다.

정확한 방법은 위치 순으로 정렬을 한다. 그리고 우체국의 위치가 마을에 있을 때 하나의 마을에 사람들을 제외 시킬 수 있기 때문에 마을이외의 곳는 우체국을 설치하지 않는다.

그렇다면 한 마을씩 왼쪽부터 탐색을 하는데 왼쪽인원과 오른쪽인원을 나눠서 왼쪽인원이 늘어나면 그만큼 거리가 늘어나고 오른쪽인원이 줄어들면 그만큼 거리가 줄어든다. 

이렇게 했을 때, 현재 거리와 다음 거리를 비교해서 거리가 줄어들지 않는다면 더 오른쪽으로 간다고 해도 줄어들지 않는다는 것을 의미하기 때문에 (왼쪽인원 만큼 줄어들고 오른쪽인원 만큼 늘어나기 때문에)

-> 다른 풀이를 보니 이를 활용해서 인원만 보고 중앙값을 넘는 인원수가 있는 마을에 설치하는 방식이였다.

import sys
input = sys.stdin.readline

N = int(input())

# 왼쪽인원
# 오른쪽인원
left_people = 0
right_people = 0
XA = []

# 저장
for _ in range(N):
    X, A = map(int,input().split())
    right_people += A
    XA.append((X,A))
# 정렬
XA.sort()

# 총거리 구하기
distance = 0
left_people += XA[0][1]
right_people -= XA[0][1]
for i in range(1,N):
    distance += abs((XA[i][0] - XA[i-1][0])*XA[i][1])

# 거리가 안줄어드는 곳 찾기
for i in range(1,N):
    if distance <= distance + (left_people - right_people)*(XA[i][0] - XA[i-1][0]):
        print(XA[i-1][0])
        break
    # 왼쪽인원만큼 늘어나고 오른쪽인원만큼 줄어든다.
    distance += (left_people - right_people)*(XA[i][0] - XA[i-1][0])
    left_people += XA[i][1]
    right_people -= XA[i][1]
else:
    print(XA[-1][0])

다른 방법 (인원의 중앙값)

import sys
input = sys.stdin.readline

N = int(input())

# 왼쪽인원
# 오른쪽인원
left_people = 0
right_people = 0
XA = []

# 저장
for _ in range(N):
    X, A = map(int,input().split())
    right_people += A
    XA.append((X,A))
# 정렬
XA.sort()

# 인원의 중앙값 찾기
for i in range(N):
    left_people += XA[i][1]
    right_people -= XA[i][1]
    if left_people >= right_people:
        print(XA[i][0])
        break