[백준 2405번] 세 수, 두 M (C++)

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

 

중위값과 평균값이 세 개 이상이 되도록 하는 숫자 3개를 고르는 문제이다.

어떻게 하면 중위값과 평균값이 가장 커질까를 생각해야하는데

숫자들을 정렬한 후에 

1. 0번째 인덱스의 숫자를 고정시키고 이후 i번째 i+1번째 숫자를 선택하여 차이가 가장 커지는 순간을 구함

2. n-1번째 인덱스의 숫자를 고정시키고 이후 i번째 i+1번째 숫자를 선택하여 차이가 가장 커지는 순간을 구함

 

1번과 2번을 모두 수행한 결과 나온 가장 큰 차이가 답이 된다.

 

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

int main() {
	int n, avg, ans, tmp;
	cin >> n;
	vector<int> v(n);
	for(int i = 0; i < n; i++){
		cin >> v[i];
	}
	sort(v.begin(), v.end());
	
	ans = -1;
	for(int i = 1; i < n-1; i++){
		avg = v[0] + v[i] + v[i+1];
		tmp = abs(avg-3*v[i]);
		ans = max(tmp, ans);
	}
	for(int i = 0; i < n-2; i++){
		avg = v[i] + v[i+1] + v[n-1];
		tmp = abs(avg-3*v[i+1]);
		ans = max(tmp, ans);
	}
	cout << ans;
}