[그리디 #10] BOJ 20115 - 에너지 드링크

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

20115번: 에너지 드링크

구현에서 문제가 발생;;

 

접근 방법

a = a + (b / 2)  을 통해 마지막 남은 드링크의 양이 최대가 되어야 한다.

b/2되는 부분이 최소가 되어야 버려지는 양이 적기 때문에

 

a: 양이 많은 것

b: 양이 가장 적은 것

 

이런 식으로 생각함.

 

1차 시도

vector 2개 v1과 v2를 만듬.

 

v2에 가장 큰 것 + (가장 작은 것 / 2)를 넣고, 추후 나머지도 넣는 방식으로 진행함.

 

sort 알고리즘을 사용했기 때문에

O(n^2*nlogn) 이기 때문에 당연하게 시간초과가 뜬다..

 

 

2차 시도

deque를 이용하면 나머지를 넣는 작업을 하지 않아도 되기 때문에 이를 이용하기로 함.

deque의 size가 1일 동안 진행하였지만 이 또한 sort를 사용하기 때문에

O(n*nlogn)이 소요된다.

 

 

정답

생각을 해보니, 가장 큰 것은 항상 고정된다.

처음에 선택한 큰 것에 계속해서 음료를 더하기 때문에 작아질 수 없기 때문!!!

 

따라서, 초기에 sort 한 번 수행후, for문 하나로 전부 더해 버릴 수 있다!!

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <deque>

using namespace std;

int n;
vector<double> v;

bool cmp(double a, double b) {
	return a > b;
}

int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);

	cin >> n;
	for (int i = 0; i < n; i++) {
		double tmp;
		cin >> tmp;
		v.push_back(tmp);
	}
	
	sort(v.begin(), v.end(), cmp);

	for (int i = n-1; i > 0; i--) {
		
		v[0] = v[0] + (v[i] / 2);
	}
	
	
	cout << v[0];

}

멍청한 청년..