(Elice /Python) 흰토끼의 장사하자

흰토끼의 장사하자

오늘도 열심히 알고리즘 공부 중인 엘리스에게 왕궁에서 은퇴한 흰토끼가 찾아왔습니다.

“엘리스! 내가 붕어빵 가게를 하나 차리려고 하는데 어느 위치에 음식점을 차려야 장사가 잘 될지 모르겠어.”

엘리스는 이런 흰토끼의 고민을 해결해줄 좋은 방법이 떠올랐습니다.

“흰토끼야, 우리 골목의 각 사람들의 거리의 합이 최소가 되는 위치에 붕어빵 가게를 차리자. 그러면 모두가 너무 멀지 않은 거리라서 자주 찾아 올거야!”

흰토끼는 붕어빵을 잔뜩 팔아 부자가 될 생각에 벌써부터 함박웃음을 짓고 있습니다. 여러분도 흰토끼의 행복한 노후를 위해 엘리스를 도와 프로그램을 완성해주세요!

 

흰토끼가 붕어빵 장사를 하려는 골목은 일직선입니다. 우리에게 주어진 정보는 골목에 있는 집들의 위치와 그 집에 사는 사람들의 정보입니다.

각 집에 사는 사람의 수를 고려할 때, 각 사람들까지의 거리의 합이 최소가 되는 위치에 붕어빵 가게를 차릴 수 있게 도와주세요.

입력 예시

5
1 3
2 7
3 10
4 5
5 5

출력 예시

3

 

입력

출력

 

입력

• 첫 번째 줄에 골목에 있는 집들의 수가 주어집니다. 이 집의 수는 1이상 100,000이하입니다.
• 두 번째 줄부터 집의 위치와 그 집에 사는 사람의 수가 공백을 기준으로 나뉘어 주어집니다. 이 수는 모두 100,000,000 이하의 자연수입니다,

출력

• 흰토끼의 붕어빵가게의 위치를 출력합니다.

소스 코드

N = int(input())

location_num = []

Max = 0

for i in range(N):
    location_num.append(list(map(int, input().split())))
    Max = max(Max, location_num[i][0])

location_num.sort()

Sum = 0
left = 0
right = 0

arr = [0 for i in range(Max+1)]

for i in range(N):
    arr[location_num[i][0]] = location_num[i][1]
    

for i in range(location_num[0][0]+1,Max+1):
    Sum+=arr[i]*(i-1)
    right+=arr[i]

Min = 999999999999999999
Min_index = 0

if Min > Sum:
    Min = Sum
    Min_index = location_num[0][0]

for i in range(location_num[0][0]+1,Max+1):
    left+=arr[i-1]
    Sum-=right
    Sum+=left
    right-=arr[i]
    #print(Sum, left, right)
    if Min > Sum:
        Min = Sum
        Min_index = i
print(Min_index)