[엘리스] 흰토끼의 장사하자

흰토끼의 장사하자

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

 

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

 

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

 

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

 

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

 

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

입력 예시

5
1 3
2 7
3 10
4 5
5 5

출력 예시

3

입력

출력

입력

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

풀이

• 완전탐색을 통한 최솟값 계산 (시간 오버)

def distance(A, j):
    sol = sum(map(lambda x: abs(x[0] - j) * x[1], A))
    return sol 

def main():
    N = int(input())
    A = []
    mindist = 1000000000000000000000000
    for i in range(N):
        x = list(map(int, input().split()))
        A.append((x[0], x[1]))

    for j in range(1, max(map(lambda x: x[0], A)) + 1):
        dist = distance(A, j)
        if mindist > dist:
            idx = j 
            mindist = dist

    print(idx)       


if __name__ == '__main__':
    main()

모범 답안

• 데이터를 정렬한 후(O(nlogn)), 정렬된 데이터 중에서 사람들간의 거리가 가장 짧은 값을 O(n)만에 계산
• temp에 위치와 사람들의 수를 dictionary로 저장
• arr은 위치와 사람들의 수를 저장
• 거리계산을 미리 저장해 둔 값으로 사용 ( 나는 하나씩 찾아서 계산했다면, 답지는 사람의 수 위치를 활용하여 계산 )
  • val : i-1번째 집에 대한 사람들간의 거리의 합
  • brr[i-1][3] * (arr[i][0]-brr[i-1][1]) : i-1번째집을 제외한 사람수만큼 줄어든 거리를 계산
    • 오른쪽으로 이동하니 거리는 줄어들 수 밖에 없음
    • 이때, i번째 집에서 i번째 집까지 거리는 0으로 반영됨
  • brr[i-1][2] * (arr[i][0]-brr[i-1][1]) : i-1번째집에서 i번째 집까지 거리를 계산
    • 이때, 이전에 계산이 안된 i-1번째 집에서 i-1번째 집의 거리가 i-1번째 집에서 i번째로 바뀌면서 계산

N = int(input())
temp = dict()

people = 0
for _ in range(N):
    X, A = map(int, input().split())
    people += A
    if X not in temp:
        temp[X] = A
    else:
        temp[X] += A


arr = []
for e in temp:
    arr.append((e, temp[e]))
arr.sort()

# print(arr)

val = 0
for e in arr[1:]:
    val += (e[0]-arr[0][0])*e[1]

# print(val)

brr = [(val, arr[0][0], arr[0][1], people-arr[0][1])]

# print(brr)

mn = val
for i in range(1, len(arr)):
    val -= (brr[i-1][3]-brr[i-1][2])*(arr[i][0]-brr[i-1][1])
    mn = min(mn, val)
    brr.append((val, arr[i][0], brr[i-1][2]+arr[i][1], brr[i-1][3]-arr[i][1]))

for i in range(len(brr)):
    if brr[i][0] == mn:
        print(brr[i][1])
        break

 

출처 : 엘리스 아카데미, https://academy.elice.io/learn