[BaekJoon] "그리디" - 백준 20115번 문제 : 에너지 드링크

[문제 설명]

https://www.acmicpc.net/problem/20115

20115번: 에너지 드링크

집에 있던 에너지 드링크들을 한 데 합쳐서, 하나의 에너지 드링크로 만들어 한번에 마시려고 함

에너지 드링크를 합치는과정 :

1. 임의의 서로 다른 두 에너지 드링크를 고름

2. 한쪽 에너지 드링크를 다른쪽 에너지 드링크에 모두 부음 (단, 붓는 과정에서 원래 양의 절반을 바닥에 흘리게 됨)

3. 다 붓고 남은 반 에너지 드링크는 버림

4. 1-3 과정을 에너지 드링크가 하나만 남을 때까지 반복

 

예를 들어, 두 에너지 드링크 a,b 가 있고, 양이 각각 Xa, Xb 라 할 때, 다음 둘 중 하나의 선택 가능

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

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

 

합쳐진 에너지 드링크의 양을 최대로 하려고 함

 

[해결 로직]

일단은, 입력된 에너지 양 리스트를 내림차순으로 정렬함

큰 수들을 앞에서 미리 더해놔야 함 --> 왜냐면, 나중에 나눌 수록 더 크게 나눠지기 때문에 작은 수가 더해짐

그런 다음 맨 첫번째, 두번째 수를 꺼냄 ( 큐 사용)

첫번째, 두번째 수를 이용해서 위의 수식에 대입한 이후 더 큰 값을 찾아내서 다시 큐의 맨 앞에 삽입

이 과정을 큐에 단 하나의 수만 남을 때까지 반복

 

[Solution 코드]

n = int(input())
from collections import deque
ary = list(map(int, input().split()))

ary.sort(reverse=True) ## 내름차순으로 정렬
drnk = 0
ary = deque(ary)

while ary: ## 큐가 빌 때가지 반복문 돌기
    ## 큰 수들을 앞에서 미리 더해놔야함
    ## 왜냐면 큰 수를 나중에 나눌 수록 더 크게 나눠지기 때문에 많은 양의 에너지를 얻을 수 없음
    fir_ener = ary.popleft()
    sec_ener = ary.popleft()

    cur_fir = fir_ener + (sec_ener/2)
    cur_sec = sec_ener + (fir_ener/2)

    drnk = max(cur_fir, cur_sec)

    ary.appendleft(drnk)

    if len(ary) == 1:
        break

print('%0.5f' %ary[0])