[백준 20115번] 에너지 드링크

문제 링크: https://www.acmicpc.net/problem/20115

20115번: 에너지 드링크

<문제 풀이> 그리디 알고리즘

 

매 순간 두 음료를 선택하여, 양이 더 적은 음료를 버린다면 에너지 드링크의 양을 최대로 만들 수 있습니다.

따라서, 우선 음료를 오름차순으로 정렬한 뒤에 가장 양이 많은 음료에 나머지 음료를 순차적으로 버리면 됩니다.

 

<C++소스코드>

#include<iostream>
#include<algorithm>
#include<vector>
#include<functional>
using namespace std;
 
int n;
double ans;
double drink[100000];
 
int main() {
    ios_base::sync_with_stdio(false);
 
    cin >> n;
    for (int i = 0; i < n; i++) {
        cin >> drink[i];
    }
 
    sort(drink, drink + n);
 
    ans = drink[n - 1];
    for (int i = 0; i < n - 1; i++) {
        ans += drink[i] / 2;
    }
    cout << ans;
 
    return 0;
}