[알고리즘/그리디] 2141번 : 우체국 - python

링크 : https://www.acmicpc.net/problem/2141

2141번: 우체국

 

---

• 문제
• 소요시간:

---

• 설계하기(접근방법) 

1. 입력받기

입력받을 마을의 개수가 많으므로 sys를 통해 입력받는다

2. 구현하기

약 30분 동안 아이디어를 고민했지만 떠오르지 않았다

 

이 문제의 답은 인구수의 중앙값이 넘어가는 지점이다

 

처음에는 해설을 보고 이해를 못해서 GPT4에게 물어봤다

 

이 처럼 좌우의 개수가 같을 때

 

가운데의 1명이 우체국의 위치를 정한다 (신기한 포인트다)

 

즉 좌, 우가 얼마나 멀든 간에

인구의 절반 지점은 항상

 

왼쪽으로 움직이면 (오른쪽의 인구수 * 1) 만큼 멀어지고 (왼쪽의 인구수 * 1)만큼 가까워진다

오른쪽으로 움직이면 (왼쪽의 인구수 * 1) 만틈 멀어지고 (오른쪽의 인구수 * 1)만큼 가까워진다

 

만약 오른쪽의 인구수가 많다면 우체국을 오른쪽으로 움직여야 한다

왼쪽의 인구수 대비 오른쪽의 인구수가 많기 때문에

오른쪽으로 움직인다면 두 인구수의 차이만큼 거리가 계속 줄어들 것이다

 

그러다 왼쪽의 인구수가 더 많아지는 순간에는 이와 반대의 상황이 나올것이다

 

위의 터미널 예시에서

현재 우체국의 위치가 9일 때,

 

9 기준 왼쪽은 5명

9 기준 오른쪽은 18명이 있다

 

거리 * 인구수 로 비교를 해야하지만, 우리는 구체적인 수치가 아닌

어느 지점이 가장 적은 거리를 나타내는가를 구하는 것이기 때문에 인구수만 비교하면 된다

 

즉 9 지점에서 오른쪽으로 1을 간다면

왼쪽은 +5

오른쪽은 - 18로

거리가 18 - 5 = 13만큼 줄어들게 된다

 

11로 가면 이젠

왼쪽은 11명

오른쪽은 12명이기 때문에

 

계속 오른쪽으로 갈수록

12- 11 = 1만큼 거리가 줄어들게 된다

 

결국 400이라는 지점에서 좌우의 균형이 맞게 되므로

왼쪽, 오른쪽 어디로 움직여도 거리가 늘어나기 때문에 그 지점이 최소 지점이 된다,

 

 

3. 출력하기

최소 거리를 출력한다

 

---

• 코드(출력)

N=int(input())
vilage=[[]for _ in range(N)]

po=0
for i in range(N):
    X,A=map(int,input().split())
    vilage[i]=[X,A]
    po+=A
now=0
vilage.sort(key=lambda x:(x[0]))
for i in range(N):
    now+=vilage[i][1]
    if now>=po/2:
        print(vilage[i][0])
        break

- 다른 분의 코드를 참고했다

---

• 얻어갈 부분

1. 시간을 아무리 주었어도 못 풀었을 것 같다. 신기한 사실을 하나 배운것에 만족했다.