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

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

 

코드

n = int(input())
drinks = list(map(int, input().split()))
drinks.sort()

ans = drinks[-1]
for i in range(len(drinks)-1):
    ans += (drinks[i]/2)

print(ans)

 

처음에는 남은 음료들 중 가장 양이 적은 2개를 골라서 합쳐야 하는줄 알았는데, 아니었다. 매 순서에 2로 나누어지는 음료들을 최대한 작게 해주어야 하는데, 이렇게 하면 그럴 수 없다.

예를 들어, 음료 5개가 가장 작은 것부터 순서대로 a, b, c, d, e 이렇게 있다고 하면 원래 생각한 방법대로면 처음에 a, b를 뽑아서 (a/2)+b를 만들게 된다. 그 다음 순서에 2개를 뽑으면 c와 d 또는 c와 (a/2)+b를 뽑게 되는데, 처음에 가장 작은 a와 b보다 양이 많은 다른 음료수를 골랐다면 2번째에 2로 나누어질 음료는 b를 고를 수 있었다. 그러니까 2개를 고를 때 가장 작은 2개가 아닌, 가장 작은 1개와 가장 큰 1개를 골라야 하는 것이다. 

 

그래서 입력을 받은 음료들을 크기 오름차순으로 정렬하고 앞의 n-1개의 음료들을 절반 나눈 값과 마지막 음료의 합을 구하도록 코드를 수정했다.