[백준 - Python] 2141 - 우체국

0.  문제 링크

 

 

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

2141번: 우체국

---

1.  풀이 방법

 

 

해당 방법은 그리디여서 어떻게 풀지 생각이 좀 많았다.

인구가 가장 많은 곳을 기준 잡고, 그 다음 많은 곳을 향해 우체국 위치를 조정할까 이런 생각을 하다가 이건 최적을 보장하지 못한다는 생각이 들어서 그만뒀다.

음..이런 문제를 풀 때, 이게 최적이라는 보장이 있을까요?

그리디는 최적을 보장하지 않습니다..

 

그래서 구글링 했는데, 그냥 순차적으로 탐색하면서 인구를 더합니다.

그러다가 전체 인구의 절반을 넘기면 해당 부분을 우체국으로 잡는다는데.....

왜?죠?

 

아무튼,,,,왜 저게 정답인지 아시는 분은 좀 알려주세요.

증명도 함께면 좋고요..

---

2.  코드

 

 

n = int(input())
maps = []
sum_population = 0
for _ in range(n):
    town, population = map(int, input().split())
    maps.append([town, population])
    sum_population += population

half_population = sum_population // 2       # 절반을 넘어가면 거기가 최적?임
maps.sort(key = lambda x: x[0])

for town, population in maps:
    sum_population -= population
    if sum_population <= half_population:
        print(town)
        break

---

3.  마무리