2141. 우체국 (Python)

2141번: 우체국

 

풀이

 그리디에 해당하는 문제인데 모르겠어서 다른 사람의 풀이를 참고했다.

 

 우체국의 위치를 구하려면 우체국을 세운 지점 기준으로 왼쪽에 위치한 사람의 숫자와 오른쪽에 위치한 사람의 숫자의 차가 최소가 되는 지점을 찾아야 한다. 먼저 입력으로 받은 마을 위치를 기준으로 오름차순 정렬한 후 처음부터 끝까지 우체국을 세워가며 왼쪽과 오른쪽 사람의 수를 누적합을 사용하여 체크한다. 두 누적 합의 차를 구하여 최소가 되는 지점을 찾고 해당 위치에 우체국을 세우면 된다.

 

 자세히는 모르겠으나 우체국을 오른쪽으로 이동하며 세우는데 이때 왼쪽에 있는 사람들의 경우는 우체국이 멀어지게 되므로 손해를 보게 되고 오른쪽에 있는 사람들의 경우는 우체국이 가까워지게 되므로 이득을 보게 된다고 볼 수 있을 것 같다. 이렇게 손해를 보는 사람과 이득을 보는 사람의 차이를 최소한으로 하여 우체국을 세우는 것이 각 사람들과 우체국까지의 거리를 최소화하는 것이기 때문에 이렇게 해결할 수 있는 게 아닐까 싶다.

 

코드

import sys
input = sys.stdin.readline

if __name__ == '__main__':
    N = int(input())  # 마을의 개수
    villages = []  # 마을 정보
    people = 0  # 총 사람 수

    for _ in range(N):
        a, b = map(int, input().split())
        villages.append((a, b))
        people += b
    villages.sort()  # 마을 위치를 기준으로 오름차순 정렬

    # 처음에는 우체국을 [0]번 마을에 세운다고 가정한다.
    left = 0  # 우체국을 세운 위치 기준으로 왼쪽에 있는 사람의 수
    right = people - villages[0][1]  # 우체국을 기준으로 오른쪽에 있는 사람의 수

    # 현재 우체국을 세운 위치, 정답이 될 우체국 위치, 왼쪽과 오른쪽 사람의 수의 차이
    idx, resIdx, subLeftRight = 0, 0, right - left

    # 우체국을 오른쪽으로 한 칸 이동하여 설치하고 왼쪽 사람의 수와 오른쪽 사람의 수를 다시 구한다.
    while idx < N-1:
        left += villages[idx][1]
        idx += 1
        right -= villages[idx][1]

        # 왼쪽, 오른쪽 사람의 수의 차이가 더 작아지면 값 갱신
        if abs(left - right) < subLeftRight:
            resIdx = idx
            subLeftRight = abs(left - right)

    print(villages[resIdx][0])