백준: 2141 우체국

문제

2141번: 우체국

 

문제 풀이

 처음 문제를 접하였을 때는 나라에서 각 사람들까지의 거리의 합이 최소가 되는 위치의 의미를 이해하지 못했다. 코드를 작성하는 시간보다 문제에서 의미하는 바를 생각하는 데까지 걸리는 시간이 더 소요된 것 같다.

 

 즉 문제를 풀기 위해서는 중간 값을 계산하고, 각 마을의 번호 순서대로 정렬한다. 정렬된 마을을 기준으로 하나씩 인구수를 계산하여 중간값과 가장 근접한 마을을 찾아 출력하면 된다.

 

코드

from sys import stdin

TOWN = 0
POP = 1

if __name__ == "__main__":
    N = int(stdin.readline())
    info = sorted([list(map(int, stdin.readline().split())) for _ in range(N)])

    mid = sum(population for _, population in info) // 2
    temp, idx = 0, 0

    while temp < mid:
        temp += info[idx][POP]
        idx += 1

    '''
    아래와 같은 Test Case 처리용, N == 2인 경우를 판단하지 않으면 99%에서 오답
    case1       case2
    2           2
    1 1         1 1
    2 1         2 2
    case 1의 경우, 1을 출력하여야 함 (마을의 인구수가 같은 경우, 번호 순대로 출력)
    case 2의 경우, 2를 출력하여야 함 (홀수인 경우)
    '''
    if N == 2:
        print(info[1][TOWN] if info[0][POP] < info[1][POP] else info[0][TOWN])
    else:
        print(info[idx - 1][TOWN])