문제접근🤔

모든 호반우를 한번에 묶는다고 가정했을때, 중앙값을 구하게 되면 중앙값보다 좋은 품질의 호반우는 절대 중앙값으로 정해질 수 없음. 모든 호반우를 묶었을때의 중앙값보다 큰 품질들을 중앙값으로 만들게 2개씩 묶어주면 됨
짝수일때, 전체 묶음의 중앙값을 찾고 그 녀석과 그것보다 작은 하나, 그리고 중앙값보다 품질들과 나머지 호반우들을 2개당 1묶음으로 묶으면 됨
홀수일때, 전페 묶음의 중앙값을 찾고 그 녀석을 혼자 묶고, 나머지는 중앙값보다 (큰 녀석, 작은 녀석) 이렇게 2개당 1묶음으로 묶으면 됨

놓쳤던 부분😅

코드😁

2416 KB

12 ms

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

int main(void) {
	int n;
	vector<int> ho;
	int answer = 0;

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	ho.resize(n);
	for (int i = 0; i < n; i++)
		cin >> ho[i];
	sort(ho.begin(), ho.end());

	if (n % 2 == 0) {
		answer = ho[n / 2] * 2;
		for (int i = n / 2 + 1; i < n; i++)
			answer += ho[i] * 2;
	}
	else {
		answer = ho[(n + 1) / 2 - 1];
		for (int i = (n + 1) / 2; i < n; i++)
			answer += ho[i] * 2;
	}
	cout << answer;
	return (0);
}