[C/C++] 백준 - 20300번 : 서강근육맨

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

20300번: 서강근육맨

문제

로니 콜먼 동영상을 보고 보디빌더가 되기로 결심한 향빈이는 PT 상담을 받으러 서강헬스클럽에 갔다. 향빈이가 서강헬스클럽을 선택한 이유는 PT를 받을 때 사용하는 운동기구를 회원이 선택할 수 있다는 점 때문이다. 하지만, 서강헬스클럽은 항상 사람이 많아서 PT를 한 번 받을 때 운동기구를 최대 두 개까지만 선택할 수 있다.

헬스장에 있는 N$N$개의 운동기구를 한 번씩 사용해보고 싶은 향빈이는 PT를 받을 때마다 이전에 사용하지 않았던 운동기구를 선택하기로 계획을 세웠다. 그리고 비용을 절약하기 위해 PT를 받을 때 운동기구를 되도록이면 두 개를 사용하기로 했다. 예를 들어, 헬스장에 총 10$10$개의 운동기구가 있을 경우 PT를 5$5$번 받으면 모든 기구를 다 사용할 수 있다. 9$9$개의 운동기구가 있는 경우에도 PT를 5$5$번 받지만, 마지막 PT를 받을 때는 운동기구를 하나만 사용한다.

하지만 향빈이는 운동기구를 선택하다가 큰 고민에 빠졌다. 왜냐하면 운동기구마다 근손실이 일어나는 정도가 다르기 때문이다. 어떤 운동기구는 자극이 잘 안 와서 근손실이 적게 일어나는데, 어떤 운동기구는 자극이 잘 와서 근손실이 많이 일어난다. 근손실이 죽음보다 무서운 향빈이는 PT를 한 번 받을 때의 근손실 정도가 M$M$을 넘지 않도록 하고 싶다. 이때, M$M$의 최솟값을 구해보자. 참고로, 운동기구를 두 개 사용해서 PT를 받을 때의 근손실 정도는 두 운동기구의 근손실 정도의 합이다.

 

 

문제가 긴데 요약하자면 주어진 근손실의 양이 짝수개면 모두 2개씩 묶고, 홀수개면 1개를 제외한 나머지를 모두 2개씩 묶는다. 이 때 2개의 합 또는 남은 하나의 값이 최소가 되어야한다.

 

직관적으로 이 문제를 보면 정렬이 일단 필요하고, 정렬을 수행한 뒤 두 수를 합했을 때 작은 값이 나오게 하려면 어떻게 해야할까? 를 고민하게 된다. 두 수를 합했을때의 값이 작게 되게 만드려면 가장 큰 수와 가장 작은 수를 더해 손실을 최소한으로 만들어야한다.

 

단, 짝수개일때는 위 같이 진행하면 되지만 홀수개일때는 가장 큰 수와 가장 작은 수를 묶는 것이 아닌, 가장 큰 수를 하나로 두고 그 직전 제일 큰 수와 가장 작은 수를 묶는 식으로 진행한다.

 

#include <algorithm>
#include <iostream>
#include <cstring>
#include <string>
#include <vector>
#include <queue>
#include <stack>
#include <cmath>
#include <ctime>
#include <set>
#include <map> 
#define fastio ios::sync_with_stdio(false), cin.tie(0), cout.tie(0)
#define ENDL cout << endl
#define ll long long	
#define ull unsigned long long
#define INF 987654321
#define Mod 1000000
#define endl '\n'
#define pil pair<int,int>

using namespace std;

int N;
vector<ll> mus;

void input() {
	cin >> N;
	mus = vector<ll>(N, 0);
	for (int i = 0; i < N; i++) cin >> mus[i];
}

ll maxValue(int left, int right) {
	ll ret = 0;
	while (left < right) {
		ret = max(ret, mus[left] + mus[right]);
		left++;
		right--;
	}
	return ret;
}

ll solution() {
	ll answer = 0;
	sort(mus.begin(), mus.end());
	if (mus.size() % 2 == 0) answer = maxValue(0, mus.size() - 1);
	else answer = max(mus[mus.size() - 1], maxValue(0, mus.size() - 2));
	return answer;
}

int main() {
	fastio;
	input();
	cout << solution() << endl;
	 
	return 0;
}