BOJ 2405 : 세 수, 두 M

 

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

2405번: 세 수, 두 M

 

문제 요약

주어지는 N개의 정수 중 세 개의 수를 골랐을 때 중위값과 평균값의 차이의 최댓값을 세 배 곱하여 출력하는 문제이다.

 

접근

선택된 세 개의 수를 오름차순으로 $a, b, c$라고 하자. 중위값은 $b$이고, 평균값은 $\dfrac{a+b+c}{3}$ 이다.

세 배 곱하여도 최대인 경우의 $a, b, c$는 변하지 않으므로
문제에서 요구하는 값(ans라고 하자.)인 세 배 곱한 값을 기준으로 설명한다.

ans $= | 3b - (a+b+c) | = | 2b-a-c |$ 이고, 이 값이 최대가 될 수 있는 경우는 2가지가 있다.

1. $c$가 $N$개 정수의 최댓값이고, $b-a$가 최소 ( ans $= c + a - 2b$ )
2. $a$가 $N$개 정수의 최솟값이고, $b-c$가 최대 ( ans $= 2b - a - c$ )

효율적인 탐색을 위해 먼저 N개의 수를 오름차순으로 정렬하고, 각각의 경우를 모두 찾아 최댓값을 구한다.

 

#include <iostream>
#include <algorithm>
using namespace std;

int main() {
	int n, arr[100000]{}, mx = 0;
	cin >> n;
	for (int i = 0; i < n; i++)	cin >> arr[i];
	sort(arr, arr + n);
	for (int i = 0; i < n - 2; i++)
		mx = max(mx, arr[i] + arr[n - 1] - arr[i + 1] * 2);
	for (int i = 1; i < n - 1; i++)
		mx = max(mx, arr[i] * 2 - arr[0] - arr[i + 1]);
	cout << mx;
}