[Python] 백준 #20115 - 에너지 드링크

문제

---

 

20115번: 에너지 드링크

코드

---

My answer (시간초과)

import sys
input = sys.stdin.readline

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

while(len(drink)!=1):
	new=min(drink)/2+max(drink)
    drink=drink[1:-1]
    drink.append(new)
print(drink[0])

Another answer

import sys
input = sys.stdin.readline

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

total=drink[-1]
for i in range(len(drink)-1):
    total += drink[i]/2
print(total)

풀이

---

그리디로 해결하는 문제로, 가장 큰 용량을 얻기 위해서는 

(가장 작은거 / 2)+(가장 큰 거)를 반복하면 된다. 

나는 우선 정렬을 해주고, 첫번째에 있는 제일 작은것과 마지막에 있는 제일 큰걸 더하고, 이 두 캔을 버린 뒤 방금 새로 만든 캔을 마지막에 다시 넣어주는 방식으로 했는데 시간초과가 나왔다.

모법 답안을 확인해보니, 내 코드는 당연히 시간초과가 나올만 했다. 어차피 새로 만든 캔은 제일 큰 것에 무언갈 더한 것이기 때문에 항상 제일 큰 캔일 것이다. 따라서 한번만 정렬하고, 그냥 리스트를 순회하면서 젤 마지막캔에다가 각 인덱스 캔의 1/2을 더해주면 해결되었다.