[BOJ][C++] 백준 20115번: 에너지 드링크 (Silver III)

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

 

문제

페인은 에너지 드링크를 좋아하는 회사원이다. 에너지 드링크는 카페인, 아르기닌, 타우린, 나이아신 등의 성분이 들어있어 피로 회복에 도움을 주는 에너지 보충 음료수이다.
야근을 마치고 한밤중에 퇴근하니 벌써 새벽 1시. 하지만 주말은 아직 멀었고, 다음 날에도 정시에 출근해야 하는 페인은 오늘도 에너지 드링크를 찾는다.
반복되는 야근에 지친 나머지, 평소보다 더 많은 에너지와 피로 회복이 필요했던 페인은 집에 있던 에너지 드링크들을 한 데 합쳐서, 하나의 에너지 드링크로 만들어 한번에 마시려 한다.
페인이 에너지 드링크들을 합치는 과정은 다음과 같다.
예를 들어, 두 에너지 드링크a, b가 있고, 양이 각각xa, xb라 할 때, 다음 둘 중 하나의 선택을 할 수 있다.
페인은 합쳐진 에너지 드링크의 양을 최대로 하려 한다. 불쌍한 페인을 도와주자!

입력

첫째 줄에 페인이 가지고 있는 에너지 드링크의 수N이 주어진다. (2 ≤N≤ 105)
둘째 줄에 각 에너지 드링크의 양이 공백으로 구분되어 주어진다.i번째 정수xi(1 ≤xi≤ 109)는 에너지 드링크i의 양이xi임을 의미한다.

출력

첫째 줄에 페인이 최대로 만들 수 있는 에너지 드링크의 양을 출력한다.
절대/상대 오차는 10-5까지 허용한다.

 

풀이

어떤 순서로 드링크를 담는지는 사실 큰 상관이 없다.

결국 한개를 제외한 모든 드링크는 최종 드링크에 절반만큼 들어갈 수밖에 없다

(하나로 합쳐지기 위해 최소 한번은 이동해야하므로)

 

따라서 제일 큰 양 하나에 나머지 드링크의 절반을 더하면 끝

// 풀이 : https://whkakrkr.tistory.com

#include <bits/stdc++.h>

using namespace std;

double solution(int &n, vector<float>&x) {
    double ans = 0;
    
    sort(x.begin(), x.end(), greater<>());
    
    ans += x[0];
    for(int i=1; i<n; i++) {
        ans += x[i]/2;
    }
    
    return ans;
}

int main() {
    ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	int n;
	cin >> n;
	vector<float>v(n);
	for(int i=0; i<n; i++) {
	    cin >> v[i];
	}
	
	cout << solution(n, v);
	
    return 0;
}