백준 2141. 우체국

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

2141번: 우체국

 

우체국은 양쪽으로 사람수가 가장 일정하게 퍼져있는 곳에 지어야 한다.

그 위치는 이분탐색으로 찾는다.

 

이분탐색으로 찾은 위치 mid 에서 왼쪽에 있는 사람들의수와 오른쪽에 있는 사람들의 수를 비교해야 하는데,

일일히 더하면 시간복잡도가 O(N^2) 가 된다.

따라서 누적합으로 구해놓으면 된다.

 

만약 마을 [1,mid] < (mid,N] 이라면 오른쪽에 사람이 더 많다는 것을 의미하기 때문에 오른쪽으로 이동한다.

아니라면 왼쪽으로 가면 된다.

 

 

 

 

 

---

그리디하게 찾는 방법도 있다.

 

우선 전체 사람수 total 을 구한다.

번호가 작은 위치부터 사람수를 더해나가다가 total 의 절반과 같거나 커지면 해당 위치가 왼쪽, 오른쪽에 사람들이 골고루 분포한 지점이다.

 

여기서 total 의 절반을 단순히 total/2 로 하면 안되고, total이 짝수라면 total/2, 홀수라면 (total+1)/2 를 해줘야 한다.