문제 링크
문제 요약
페인은 N개의 에너지 드링크를 가지고 있습니다. 이 드링크들을 하나로 합치려 하는데, 두 드링크를 합칠 때 한쪽 드링크를 다른 쪽에 붓는 과정에서 붓는 양의 절반이 손실됩니다.
즉, A와 B를 합치면 A + B/2 또는 B + A/2가 됩니다.
이 과정을 드링크가 하나 남을 때까지 반복할 때, 최종적으로 얻을 수 있는 에너지 드링크의 최대 양을 구해야 합니다.
풀이
문제는 N개의 에너지 드링크를 합쳐 하나의 드링크로 만들 때, 그 양을 최대로 만드는 방법을 찾는 것입니다. 핵심은 두 드링크 xa, xb를 합칠 때 xa + xb/2 또는 xb + xa/2 중 하나가 된다는 점입니다. 여기서 주목할 점은 붓는 양의 절반이 손실된다는 것입니다. 즉, xb/2 또는 xa/2만큼의 양이 손실됩니다.
최종 양을 최대로 하려면 손실되는 양을 최소화해야 합니다. 이를 위해 Greedy (그리디, 탐욕법) 전략을 사용할 수 있습니다.
-
가장 많은 양을 가진 드링크를 보존: 가장 많은 양을 가진 드링크는 절대로 다른 드링크에 붓지 않아야 합니다. 만약 가장 많은 양의 드링크를 다른 드링크에 붓는다면, 그 드링크 양의 절반이 손실되어 버리기 때문에 최종 결과에 큰 손실을 가져옵니다. 따라서 가장 양이 많은 드링크
MAX_X를 기준으로 삼고, 이 드링크에 나머지 드링크들을 합쳐야 합니다. -
나머지 드링크들을
MAX_X에 합치기: 나머지N-1개의 드링크x_i들은 모두MAX_X에 붓습니다.x_i를MAX_X에 부으면MAX_X의 양은MAX_X + x_i / 2가 됩니다. 이 과정을 모든N-1개의 드링크에 대해 반복합니다.
결과적으로, 최종 에너지 드링크의 양은 (가장 양이 많은 드링크의 양) + (나머지 모든 드링크 양의 합) / 2가 됩니다.
정답 코드
def solve():
n = int(input())
l = sorted([*map(int, input().split())])
print(sum(l[:-1]) / 2 + l[-1])
if __name__ == "__main__":
tc = 1
for t in range(1, tc+1):
ret = solve()