BOJ 2405 세 수, 두 M

세 수의 중위 값은 정렬했을 때 가운데 오는 값이고, 세 수의 평균값은 세 수의 합을 3으로 나눈 값이다. 최대 10만개의 수가 주어질 때, 중위값과 평균값의 차이가 최대가 되도록 세 수를 선택하고, 그 중위값과 평균값의 차이(최대값)를 구하는 문제이다.

음 평균값과 중위값의 차이가 커지려면 어떻게 해야할까?
일단 중위값을 편하게 구하기 위해서 주어진 수들을 오름차순으로 정렬해본다.
100 120 234 430 489 여기서 어떤 세 수를 고르든 중위값은 맨 앞, 맨 뒤 값을 제외한 수들 중 하나가 될 것이다. 중위값을 먼저 선택했다고 치자. 그럼 나머지 수는 중위값의 왼쪽에서 하나, 오른쪽에서 하나를 골라야 한다. 어떤 수를 골라야 평균값이 중위값에서 멀어질까? 일단 b값은 정해졌으니 a, c값만 생각하자. a+c값이 최대한 크거나 최대한 작아야 평균값이 중위값에서 멀어질 것이다. b값은 정해져있고 (a+b+c)/3이 평균이므로 a+c가 최대가 되거나 a+c가 최소가 되는 수를 골라야 평균값이 중위값에서 멀어질 가능성이 높다. (a+c)/2의 값이 b에 가까우면 안되고 최대한 멀어지려면 a+c값이 최대가 되도록 혹은 a+c값이 최소가 되도록한 것 둘 중하나가 b에서 멀 것이다.

막 확실하게 증명할 수 있거나 와 닿는 것은 아니지만... 맞는 것 같다.
그럼 정렬된 상태에서 b(중위값)을 기준으로 왼쪽에서 가장 큰 값, 오른쪽에서 가장 큰 값을 이용해서 값(평균값과 중위값의 차이)을 구해보고, 왼쪽에서 가장 작은 값, 오른쪽에서 가장 작은 값을 이용해서 값을 구해본 후 두 값을 비교해서 둘 중 큰 값을 선택하면 된다.

정렬을 했다면 , 중위값 양쪽 구간의 각 최소값, 최대값은 바로 구할 수 있다.
그럼 중위값을 2번째 값부터 n-1번째 값까지로 보면서 하면 O(n)만에 풀 수 있겠다.

주의할 점은 평균값을 구하기 위해 3으로 나누면 나머지가 버려지므로... 어차피 답에서 3을 곱해서 출력하라고 했으니 평균값을 구할 때 3으로 나누지말고, 그냥 중위값*3과의 차이를 계산하면 될 것 같다.
AC를 받았다.