문제접근
•
모든 호반우를 한번에 묶는다고 가정했을때, 중앙값을 구하게 되면 중앙값보다 좋은 품질의 호반우는 절대 중앙값으로 정해질 수 없음. 모든 호반우를 묶었을때의 중앙값보다 큰 품질들을 중앙값으로 만들게 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);
}
C++
복사
