[백준] 20115 에너지 드링크

문제

• A와 B 에너지 드링크를 고르면 둘 중 하나는 절반만 남길 수 있다.
• 합쳐진 에너지 드링크 양의 최댓값은?
• 2 <= N <= 10^5
  1 <= 에너지 드링크 양 <= 10^9

 

풀이

• 합칠 때마다 절반의 양이 사라지기 때문에 양이 적은 애들을 고르는게 좋다.
• 따라서 가장 양이 많은 에너지 드링크에 차례로 절반씩 부으면 된다.

 

import heapq

N = int(input())
drinks = sorted(list(map(int, input().split())))
answer = drinks.pop()
h = []
for i in drinks :
    heapq.heappush(h, i)          

while h :
    one = heapq.heappop(h)
    answer += one/2

print(answer)

 

References

• 백준 그리드