[BOJ] 2405 - 세 수, 두 M

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

BOJ - 세 수, 두 M

문제 유형: 그리디, 정렬, 수학

문제 난이도: Gold IV

시간 제한: 2초

메모리 제한: 128MB

 

문제

n개의 정수 A[1], A[2], …, A[n]이 있다. 서로 다른 세 정수 i, j, k에 대해서 a = A[i], b = A[j], c = A[k]라 하자. 세 수의 중위(Median)값은 정렬했을 때 가운데에 오는 수가 된다. 세 수의 평균(Mean)값은 (a+b+c)÷3이 된다.

만약 세 수가 5, 2, 5라면 중위값은 5, 평균값은 4가 된다. 세 수가 2, 3, 1이라면 중위값은 2, 평균값도 2가 된다.

n개의 수들이 주어졌을 때, 위와 같이 세 수를 선택하여(i, j, k가 서로 다르도록) 중위값과 평균값의 차이가 최대가 되도록 해 보시오.

 

입력

첫째 줄에 정수 n(3 ≤ n ≤ 100,000)이 주어진다. 다음 n개의 줄에는 n개의 정수들이 주어진다. 각 수들의 절댓값은 100,000,000을 넘지 않는다.

 

출력

첫째 줄에 중위값과 평균값의 차이를 세 배 한 값을 출력한다.

 

풀이

배열을 정렬시키고, 중위 값을 기준으로 얻을 수 있는

- 최소의 평균값 케이스(가장 작은 값은 맨 왼쪽, 가장큰 값은 중위 + 1의 인덱스)와

- 최대의 평균값 케이스(가장 작은 값은 맨 중위 - 1의 인덱스, 가장큰 값은 맨 끝의 인덱스)

를 구한다.

 

정답(중위값과 평균값의 차이를 세 배한 값) 후보는 세 수들의 |(최소값) + (최대값) - 2 * (중앙값)|이다.

이는 식을 정리하면 나온다.

 

모든 중위 값에서 얻을 수 있는 모든 값들을 구하고, 이들 중 최대값을 출력하면 된다.

 

 

코드

C++

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int main(int argc, char *argv[]) {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n;
    cin >> n;

    vector<ll> a(n);
    for (auto &i : a) cin >> i;

    sort(a.begin(), a.end());

    ll ans = LLONG_MIN;
    for (int median = 1; median < n - 1; median++) {
        int minleft = 0;
        int minright = median + 1;
        ll minSum = abs(a[minleft] + a[minright] - 2 * a[median]);

        int maxleft = median - 1;
        int maxright = n - 1;
        ll maxSum = abs(a[maxleft] + a[maxright] - 2 * a[median]);

        ans = max({ans, minSum, maxSum});
    }

    cout << ans << "\n";

    return 0;
}