[파이썬] 백준 20115 에너지 드링크

문제 링크

www.acmicpc.net/problem/20115

20115번: 에너지 드링크

문제 요약

두 에너지 드링크 a, b가 있고, 양이 각각 Xa, Xb라 할 때, 다음 둘 중 하나의 선택을 할 수 있다.

• a의 양을 Xa + (Xb / 2)로 만들고, b를 버리기

• b의 양을 Xb + (Xa / 2)로 만들고, a를 버리기

위의 방식으로 에너지 드링크를 합쳐서 그 양을 최대로 하자.

 

접근

그리디 문제이고 접근법도 굉장히 쉽습니다.

 

그냥 가장 양이 많은 드링크에 그다음 양이 많은 드링크를 부어버리면 됩니다.

 

이 과정을 하나의 드링크만 남을 때까지 반복하면 되는 문제입니다.

 

코드

import sys
input = sys.stdin.readline
 
n = int(input())
a = list(map(int,input().split()))
a.sort(reverse=True)
sum = a[0]
for i in range(1,n):
    sum += (a[i]/2)
print('%g'%sum)