[백준 20300] 서강근육맨

문제

www.acmicpc.net/problem/20300

20300번: 서강근육맨

 

풀이

구해야 하는 건 기구를 두 개씩 사용해서 일어나는 근손실의 합의 최대를 M이라 할 때, 이를 최소화해야 합니다.

"최대의 최소화" 꼴이라 이분 탐색도 가능하지만 그보다 간단하게 근손실의 정도를 오름차순으로 정렬하고, 매칭 되지 않은 오른쪽 끝 값(최대 값)을 왼쪽 끝 값(최소 값)과 매칭시켜주는 방법을 통해 해결할 수 있습니다.

(n이 홀 수일 경우에 한 번은 1개의 기구만 선택해야 하므로 이는 최대 값을 선택한 후, 정렬한 구간 [0 ~ n-2]의 기구들을 매칭 해주면 됩니다. 

 

코드

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

int n;
ll ans;
vector<ll> t;

int main() {
	cin.tie(NULL); cout.tie(NULL);
	ios_base::sync_with_stdio(false);

	cin >> n;
	t.resize(n);
	for (ll& i : t) cin >> i;
	sort(t.begin(),t.end());
	if (n % 2) {
		ans = t[n - 1];
		for (int i = 0; i < (n - 1) / 2; i++)
			ans = max(ans, t[i] + t[n - 2 - i]);
	}
	else {
		ans = t[0] + t[n - 1];
		for (int i = 1; i < n / 2; i++)
			ans = max(ans, t[i] + t[n - 1 - i]);
	}
	cout << ans;
}