[백준] #2141 우체국 (python)

2141번: 우체국 (acmicpc.net)

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 이며 모든 입력은 정수이다.

출력

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

 

예제 입력 1 복사

3
1 3
2 5
3 3

예제 출력 1 복사

2

 

# Code

import sys

input = sys.stdin.readline

X = []
people = 0
n = int(input())
for i in range(n):
    village, num = map(int,input().split())
    X.append([village, num])
    people+=num

X.sort(key = lambda x : x[0])

count = 0
po = 0
for i in range(n):
    count+=X[i][1]
    if count >= people/2:
      po = X[i][0]
      break 

print(po)

# Comment

저번 주에도 풀어보려고 고민하다가 결국 못 풀어서 오늘로 미뤘는데 오늘도 못 풀었다. 어쩔 수 없이 풀이를 봤는데 마을에 있는 사람들의 수를 순차적으로 더해서 마을 당 인구의 누적 합이 총 인구 수의 절반 이상이 될 때 그 마을에 우체국을 세우는 것이 해답이라고 한다. 근데.. 이렇게 푸는 거라는 말만 있고 왜 그런지는 찾지 못했다... ㅠㅠ.. 이런 문제 내도 되나요? 수학 머리가 없으니까 알고리즘도 못 풀고 아주 슬프다.

하여튼 풀이가 저거라고 하니.. 그에 맞춰서 코드를 짜보았다.

1. X 리스트에 마을 번호와 사람 수를 각각 넣어주고, 총 사람 수를 알아내기 위해 사람 수를 입력받을 때마다 people 변수에 더해준다.
2. 마을 번호가 순서대로 주어지지 않을 경우를 대비해서 마을 위치를 오름차순으로 정렬해준다.
3. po : postoffice 즉, 우체국의 위치를 출력할 변수이다. for문을 돌면서 count 변수에 각 마을 당 사람 수를 누적해서 더해가면서 그 합이 총 사람 수의 절반 이상이 되었을 때 break 걸어주고 해당 마을의 위치를 저장하여 출력해준다.

** 몇 번 틀리던 부분이 있었는데 people/2 가 아닌 people//2 로 적어서 틀렸었다.. people//2 로 쓰면 소수점이 나오면서 나눠지는 경우에도 뒤의 소수점은 빼고 정수 값만 구하기 때문에
예를 들어서 31명이 있을 경우 /2 하면 15.5가 나와서 누적합이 16명인 마을이 나왔을 때 이 마을의 위치를 출력해야 하는데, //2를 썼을 경우 15가 나와서 누적합이 15인 마을의 위치를 출력하고 끝내는 사태가 발생할 수 있다. 
아마 풀이 자체가 누적합이 절반 이상인 마을을 구해야 하기 때문에 이렇게 해야 하는 것 같다.. 왜 인지는.. 더 고민하는 걸로.