[백준] 2405 세 수, 두 M

문제를 요약해보면 세개의 수를 정했을 때

중위값과 평균값의 차이가 최대가 되도록 하고 그 값의 3배를 출력하면 된다!

우리는 수학적으로 문제에 접근해야 한다

세 수를  a,b,c라고 하자 (a<b<c)

그럼 중위값은 b 이고 평균값은 (a+b+c)/3 이다

문제에서 원하는 값은 b-{(a+b+c)/3}이므로 (a-2b+c)/3으로 볼 수 있다!

그리고 착하게 3배한 값을 출력하라 했으므로 

결국은 (a-2b+c)의 최대값이 된다

여기서..! 난 한심하게 a,c를 고정시켜버리고 b를 구했는데

그러면 안된다 ㅋㅋㅋ

차이니까 2가지 경우로 나뉜다

1) (a-2b+c) => c를 고정시키기

2) (-a+2b-c) => a를 고정시키기

고정시키고 돌면 최대 20만번이면 확인가능하다!

소스코드

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
#define ll long long
ll n, arr[100010];
 
int main() {
    scanf(" %lld", &n);
    for (int i = 0; i < n; i++) scanf(" %lld", &arr[i]);
    sort(arr, arr + n);
    ll ans = 0;
    for (int i = 0; i < n - 2; i++) ans = max(ans, abs(arr[n - 1] + arr[i] - arr[i + 1] * 2));
    for (int i = 1; i < n - 1; i++) ans = max(ans, abs(-arr[0] + arr[i] * 2 - arr[i + 1]));
    printf("%lld\n", ans);
}