[백준] 20115번 에너지 드링크

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

20115번: 에너지 드링크

 

풀이

에너지 드링크가 가장 많은 양이될 수 있게 절반을 버리기 위해서는 항상 적은쪽을 버리면 된다.
가장 많은쪽을 버리지만 초기에 가장 많이 담겨있던 에너지 드링크를 버리지 않는 경우가 가장 적게 버리기 때문에
역순으로 정렬하여 풀었다.

 

energys = list(map(int, input().split()))
energys.sort(reverse = True)
energys = deque(energys)

에너지 드링크 정보를 받은 뒤에 내림차순으로 정렬하고 deque를 이용하여 앞에서부터 꺼내서 사용했다.

 

A = energys.popleft()

초기값 설정

 

while energys:
    B = energys.popleft()

    if A > B:
        A += B/2
    else:
        A = B + A/2

이후 값을 비교하여 적은 쪽이 절반이되게 풀었지만
내림차순으로 정렬되어있기 때문에 항상 새로 나오는 B가 절반이 된다.

 

print(round(A, 5))

절대/상대 오차는 10-5까지 허용한다.
라는 조건을 만족시키기 위해서 round 함수를 사용했다.

 

 

전체 코드

from collections import deque

N = int(input())

energys = list(map(int, input().split()))
energys.sort(reverse = True)
energys = deque(energys)

A = energys.popleft()


while energys:
    B = energys.popleft()

    if A > B:
        A += B/2
    else:
        A = B + A/2

print(round(A, 5))

그리디 문제의 경우 그리디라는 점을 파악만하면 쉽게풀 수 있는 것 같다.