[백준/C++] 20115번: 에너지 드링크

20115번: 에너지 드링크 문제 바로가기

문제 분석

1. 서로 다른 에너지 드링크 2개를 골라 하나의 에너지 드링크의 절반을 다른 에너지 드링크에 붓는다.

2. 에너지 드링크 하나가 남을 때까지 반복하고, 합쳐진 에너지 드링크의 양을 출력하는 문제

이때, 합쳐진 에너지 드링크의 양을 최대로 하는 값 출력

---

문제 풀이 과정

절반을 다른 쪽에 부어서 에너지 드링크의 양을 최대로 해야하는 상황에서 가장 먼저 든 생각

💡 무조건 가장 큰 양의 드링크에 가장 작은 양의 드링크를 붓자 !

그래야 가장 작은 양의 에너지 드링크를 버리면서 큰 양을 유지할 수 있기 때문

1. 에너지 드링크를 오름차순으로 정렬
2. ans에 가장 큰 양의 드링크 저장
3. 가장 작은 양의 드링크부터 순서대로 절반씩 ans에 더해줌

→ N-1개까지 수행하면 최대의 양을 가진 에너지 드링크 얻을 수 있다 !

의문점

어째서 가장 큰 값을 갱신하지 않고, 바로 ans에 더해줘도 최대로 구할 수 있을까?

→ 당연하다. 애초에 오름차순으로 정렬해서 가장 큰 값이 맨 오른쪽에 있는 상황에서 계속 그 값에 절반을 부어주면 그 값은 계속해서 최대값을 가질 수 밖에 없으므로 ans에 계속 더하는 방식으로 수행하면 된다.

---

코드

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

int N;
double ans;
vector<double> drink;

int main() {
    cin >> N;
    for (int i = 0, x; i < N; i++) {
        cin >> x;
        drink.push_back(x);
    }
    sort(drink.begin(), drink.end());
    ans = drink.back();
    
    for (int i = 0; i < N - 1; i++) {
        ans += (drink[i] / 2);
    }
    cout << ans;
    
    return 0;
}