안테나 C++ - 백준 18310

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

그리디 문제.

처음에는 평균에 가까운 수가 답이라고 생각했지만 틀렸다.

문제 접근

입력 :
5
1 4 8 10 17 의 예시는 다음과 같다.

위 그림을 보면 중앙값에서 안테나 부터 집들의 거리가 최소가 되는 것을 볼 수 있다.

이는 한 가지는 예시를 보면 알 수 있다.

참고

맨 왼쪽 집부터 맨 오른쪽 집까지 간다고 해보자.

첫번째 집을 지나고서 부터는 첫번째 집과는 멀어지지만 다른 집들과는 가까워진다.

두번째 집을 지날 때에는 안테나와 모든 집의 거리가

첫번째 집과 두번째 집 사이의 거리 차 만큼만 늘어났고 나머지 집들과는 줄어들었다.

(사실상 감소, 오른쪽 집들과 가까워진 거리가 더 크다.(오른쪽 집의 개수가 더 많음))

두번째 집을 지나고 세번째 집을 지날 때 두번째 집과 세번째 집 사이의 거리 차 만큼만 늘어났고

다른 집들과의 거리는 감소했다. (사실상 감소, 오른쪽 집들과 가까워진 거리가 더 크다.(오른쪽 집의 개수가 더 많음))

이 양상은 오른쪽 집에서 출발해도 동일하다.

따라서 중앙값이 답이 된다.

코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int main(){
	int n; cin >> n;
	vector<int> v(n); for(int i=0;i<n;i++){cin >> v[i];}
    sort(v.begin(),v.end()); if(n==1){cout << v[0]; return 0;}
    cout << v[(n-1)/2];
}