그리디 알고리즘 - 거리의 합이 최소가 되는 위치를 찾는 방법

1. 문제1

 

18310번: 안테나 (acmicpc.net)

18310번: 안테나

 

2. 풀이

 

수직선 위에 위치한 점 중에서 모든 점까지 거리 합이 최소인 점의 좌표는 어떻게 찾을 수 있을까

 

직관적으로는 점의 좌표를 오름차순으로 정렬하고 당연히 중앙에 위치한 점이 모든 점까지 거리 합이 최소인 점일텐데

 

왜 그런지를 한번 생각해본다면..

 

수직선 위에 집이 있을때, 맨 왼쪽 집에서부터 시작해서 오른쪽으로 한칸씩 이동한다고 생각해보자

 

 

1부터 시작해서 오른쪽으로 이동한다고 해보면...

 

왼쪽 집 1개와 거리가 +1

 

하지만 오른쪽 집 3개와는 각각 거리가 -1이 되어 전체 -3이 된다

 

그러니까 오른쪽으로 1칸씩 이동할때마다 전체 거리 합은 -2씩 될거다

 

 

그러면 계속 오다가 파란색까지 오게 되었을때, 다시 오른쪽으로 1칸 이동한다고 해보자

 

그러면 왼쪽과의 거리는 +2

 

오른쪽과의 거리는 -2

 

그리고 계속 가다가 7번에 오는 순간? 

 

왼쪽 집들과의 거리는 +3, 오른쪽 집과의 거리는 -1이 되어 이제는 거리 합이 증가하기 시작한다

 

 

그래서 중앙에 있는 5번을 기준으로 5번까지 오면 거리 합이 감소하는 위치이고, 5번을 넘어가서부터는 거리 합이 증가한다

 

일반적으로 생각해보면..

 

맨 왼쪽부터 오른쪽으로 이동을 할때, 왼쪽 집과의 거리는 +1씩 늘어나고, 오른쪽 집과의 거리는 -1씩 감소할것이다.

 

맨 왼쪽부터 이동하니까, 당연히 왼쪽 집의 개수 < 오른쪽 집의 개수가 되겠지

 

오른쪽 집의 개수가 더 많으니까, 거리 합이 감소하는 양이 거리 합이 증가하는 양보다 많아서, 전체 거리 합은 감소할 것이다

 

그러다가 어느 순간 까지 오면, 왼쪽 집의 개수 > 오른쪽 집의 개수가 되는 순간이 있다

 

이럴때 오른쪽으로 이동하면, 거리 합이 감소하는 양이 거리 합이 증가하는 양보다 적어서, 전체 거리 합이 증가할 것이다.

 

따라서 전체 거리 합이 최소가 되는 지점은, 왼쪽 집의 개수 = 오른쪽 집의 개수가 되는 지점이다.

 

이를 반드시 만족하는 지점이 바로 중앙값이다.

 

중앙값은 그 지점을 기준으로 왼쪽에 있는 지점의 개수와 오른쪽에 있는 지점의 개수가 같은 지점이다.

 

from sys import stdin

n = int(stdin.readline())

house = list(map(int,stdin.readline().split()))

house.sort()

if n % 2 == 0:
    
    print(house[n//2-1])

else:
    
    print(house[n//2])

 

 3. 문제2

 

2141번: 우체국 (acmicpc.net)

2141번: 우체국

 

 

4. 풀이2

 

위의 원리를 이해하고 조금 응용해야 풀 수 있는 문제

 

이번엔 수직선 상에서 각 점이 가중치를 가지고 있어서 무조건 중앙값을 출력하는게 아니라

 

거리 계산에 신경을 써야돼

 

점의 가중치(=우체국 사람 수)는 생각하지 말고 점의 위치를 기준으로 정렬을 수행한다

 

from sys import stdin

n = int(stdin.readline())

post = []

total_human = 0

for _ in range(n):
    
    x,a = map(int,stdin.readline().split())

    post.append((x,a))

    total_human += a

post.sort()

 

그리고 똑같이 맨 왼쪽에서 오른쪽으로 이동을 할거야

 

왼쪽 우체국까지 거리합은 0

 

오른쪽 우체국까지 거리합은? 전체 사람수 total_human이겠지

 

왜냐하면 어떤 점까지 거리합은 점이 가지는 가중치(=사람 수)로 계산하니까

 

그러면 이제 왼쪽에서 오른쪽으로 이동하기 시작할거야

 

left = 0
right = total_human

for i in range(n):
       
    dleft = left + post[i][1]
    dright = right - post[i][1]

    if dleft >= dright:
        
        break
    
    else:
        
        left = dleft
        right = dright

print(post[i][0])

 

 

오른쪽으로 1번 이동하면,

 

왼쪽에 있는 우체국의 사람수는 이동한 우체국에 존재하는 사람 수만큼 더해지고

 

오른쪽에 있는 우체국의 사람수는 이동한 우체국에 존재하는 사람 수만큼 빼지겠지

 

그러면서 왼쪽에서는 사람수가 더해지는 만큼, 거리 합이 증가하고 오른쪽에서는 사람 수가 빼지는 만큼 거리 합이 감소하는 것이다

 

그러면 언제까지 이동해야 거리 합이 최소가 될까?

 

왼쪽에 있는 우체국의 사람 수가 어느 순간 오른쪽에 있는 우체국의 사람 수보다 커지는 순간

 

전체 사람까지 거리 합이 최소가 될 것이다

 

아까는 같을때 최소라며??

 

근데 dleft와 dright가 같은 지점이 존재하지 않을수도 있겠지

 

그러면 dleft < dright인데... dleft가 dright에 최대한 근접할때 최소일수도 있잖아???

 

그러네... 가 아니고... left,right에 더해지고 빼지는 양이 다를때 성립하는데

 

지금은 left와 right에 더해지는 양이 post[i][1]로 동일하니까... 계속 더해나가다가 왼쪽이 더 커지면 종료하면 된다

 

from sys import stdin

n = int(stdin.readline())

post = []

total_human = 0

for _ in range(n):
    
    x,a = map(int,stdin.readline().split())

    post.append((x,a))

    total_human += a

post.sort()

left = 0
right = total_human

for i in range(n):
       
    dleft = left + post[i][1]
    dright = right - post[i][1]

    if dleft >= dright:
        
        break
    
    else:
        
        left = dleft
        right = dright

print(post[i][0])

 

뭔가 뭔가하네... 흐으므