[C++][BOJ 20117 호반우 상인의 이상한 품질 계산법]정렬

BOJ 20117

 

문제 자체가 어렵지 않다. gold 5

 

[힌트]

가장 비싸게 팔 수 있는 방법은 가장 비싼 것과 싼 것을 묶어라.

 

 

[문제 풀이]

짝수 묶음의 경우 (a, b) (a<b)묶었을 경우 b가 중간값이 된다.

따라서 정렬 후 큰 것과 작은 것 2개씩 묶음으로 생각해서 계산을 했다.

마지막에 홀수면 하나 남은 것을 더해준다.

 

 

[소스 코드]

#include <bits/stdc++.h>
using namespace std;
int main(){
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int n;	cin>>n;
	int qual[n];
	for(int i = 0 ; i < n ;) cin>>qual[i++];
	sort(qual,qual+n);
	
	int max_profit = 0; 
	for(int i = n-1 ;  i >= (int)((n+1)/2) ; i-- ){
		max_profit += qual[i];
	} 

	max_profit = (n%2==0) ? max_profit*2 : max_profit*2 + qual[n/2]; 
	cout<<max_profit;
}