C++ / 백준 / 20300 / 서강근육맨

문제

 

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

20300번: 서강근육맨

문제풀이

 

몇 가지 경우만 생각해서 최댓값을 구하면 되나 싶었는데, 경우가 많은 거 같아서 다 탐색했다.

 

운동기구가 짝수면 정렬을 하고 맨 앞, 맨뒤 두 개를 선택하고 맨 앞은 그다음 맨 앞, 맨뒤는 그다음 맨뒤를 선택해 가면 된다.

 

운동기구가 홀수인 경우는 운동기구 하나는 반드시 남게 된다. 

정렬을 하여 가장 무거운 운동기구를 하나 남기면 나머지는 짝수개가 된다.

짝수개와 마찬가지로 양쪽 끝 두 개를 선택해 가면서 최댓값을 출력하면 된다.

 

코드

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
#define END loss.size() -1
using namespace std;

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

	ll N(0), idx(0), answer(0);

	cin >> N;
	vector<ll>loss(N, 0);
	for (idx = 0; idx < N; ++idx) {
		cin >> loss[idx];
	}

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

	if (N % 2 == 0) {
		for (idx = 0; idx < N/2; ++idx) {
			answer = max(answer, loss[idx] + loss[END - idx]);
		}
	}
	else if (N % 2 != 0) {
		answer = loss[END];
		for (idx = 0; idx < N / 2; ++idx) {
			answer = max(answer, loss[idx] + loss[END - 1 - idx]);
		}
	}
	cout << answer;
}