백준 20115번 [에너지 드링크](C++) -yes6686- 티스토리

백준 문제 풀이: 20115 [에너지 드링크]

---

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

문제 설명:

N개의 에너지 드링크가 주어집니다. 한 번에 최대한의 에너지를 얻기 위해서는 한 개의 드링크에 다른 드링크를 섞습니다. 섞인 드링크의 양은 원래 드링크 양의 절반입니다. 최대 에너지 드링크의 양을 계산하는 문제입니다.

---

문제 해결 코드

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

double arr[100001]; // 에너지 드링크의 양

int main() {
    int n;
    cin >> n;

    // 에너지 드링크의 양 입력
    for (int i = 0; i < n; i++) {
        cin >> arr[i];
    }

    // 에너지 드링크를 오름차순으로 정렬
    sort(arr, arr + n);

    // 가장 큰 양의 드링크를 기준으로 나머지를 섞음
    double ans = arr[n - 1]; // 가장 큰 드링크 양
    for (int i = 0; i < n - 1; i++) {
        ans += arr[i] / 2.0; // 나머지 드링크는 절반만 추가
    }

    // 결과 출력
    cout << ans << '\n';

    return 0;
}

---

코드 설명

• 핵심 아이디어: 에너지 드링크의 양을 최대로 만들기 위해 가장 큰 값을 기준으로 나머지 값을 섞습니다. 섞는 순서는 결과에 영향을 미치지 않으므로 정렬 후 계산합니다.
• 구현 세부사항:
  • 배열을 정렬하여 가장 큰 값을 기준으로 설정
  • 나머지 드링크는 절반의 양을 결과에 추가
• 시간 복잡도 분석: O(n log n)
  • 정렬에 O(n log n)의 시간이 소요
  • 나머지 드링크를 순회하며 계산하는 데 O(n)

---

결과

최대 에너지 드링크의 양을 정확히 계산합니다. 배열 정렬을 활용해 간단하고 효율적으로 문제를 해결했습니다.

다른 접근 방식이나 개선 사항이 있다면 댓글로 공유 부탁드립니다!