백준 BOJ 20300 - 서강근육맨

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

20300번: 서강근육맨

배열에서 두 수 $t_a$ 와 $t_b$ 를 골라 더해서 $K$를 만들고,

이 $K$들의 최댓값이 최소가 되도록 하는 문제.

 

더하는 두 수를 선택하는데 있어서,

정렬된 배열의 양 끝, $MAX_t$ 와 $MIN_t$ 를 더하는게 $K$를 작게 만들수 있는 방법이다.

가장 큰 수와 가장 작은수를 매칭시켜줘야 가장 큰수에 최소한의 수를 더할 수 있기 때문이다.

 

이 방법으로 배열의 크기가 짝수라면 깔끔하게 해결되지만,

배열의 크기가 홀수라면 운동기구를 하나만 사용해서 $K$를 만들게 된다.

 

가장 큰수와 가장 작은수를 매칭시켜주어야 한다는 규칙에 따라,

가상으로 수 0을 배열에 합쳐준다고 생각하면 수 매칭을 앞선 경우와 동일하게 해결해줄 수 있고,

이때는 가장 큰 수와 가장 작은 수0 를 서로 매칭하게 되므로

가장 큰수만 따로 $K$ 로 빼주고

이 $K$들의 최댓값을 구하면 정답이 된다.

 

#include <bits/stdc++.h>
using namespace std;
typedef unsigned long long ll;

vector<ll> in;
vector<ll> v;

int main(){
	ll N,a;
	
	cin >> N;
	for(int i=0; i<N; i++){
		cin >> a;
		in.push_back(a);
	}
	
	sort(in.begin(), in.end());
	
	
	if(N%2) v.push_back(in[--N]);
	
	for(int i=0; i<N/2; i++){
		v.push_back(in[i]+in[N-i-1]);
	}
	
	ll ans = 0;
	for(auto k : v) ans = max(ans, k);
	cout << ans;
	return 0;
}