[BOJ] 20115번 에너지 드링크 (C++)

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

20115번: 에너지 드링크

 

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

int main() {
	int n;
	double num;
	vector<double> v;
	cin >> n;
	for(int i = 0; i < n; i++){
		cin >> num;
		v.push_back(num);
	}
	sort(v.begin(), v.end());
	
	double sum = v[n - 1];
	for(int i = 0; i < n - 1; i++){
		if(v[i] < sum) sum += v[i] / 2;
		else sum = sum / 2 + v[i];
	}
	cout << sum << endl;
	return 0;
}

 

먼저 각 에너지 드링크 양을 오름차순으로 정렬한다. 

2 3 6 9 10

 

가장 큰 값을 초기 sum으로 두고  sum = 10

 

합쳐진 에너지 드링크의 양을 최대로 하려 하므로

벡터에 있는 수를 차례로 sum과 비교하여 둘 중 작은 수를 2로 나누어 더한다.

2 < 10        sum = 1 + 10 = 11

3 < 11        sum = 1.5 + 11 = 12.5

6 < 12.5      sum = 3 + 12.5 = 15.5

9 < 15.5      sum = 4.5 + 15.5 = 20