Algorithm (PS)

[백준] 20115번: 에너지 드링크 (Python/파이썬) - Greedy

minjiwoo 2022. 12. 25. 21:03
728x90

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

 

20115번: 에너지 드링크

페인은 에너지 드링크를 좋아하는 회사원이다. 에너지 드링크는 카페인, 아르기닌, 타우린, 나이아신 등의 성분이 들어있어 피로 회복에 도움을 주는 에너지 보충 음료수이다. 야근을 마치고 한

www.acmicpc.net

요상하게 요즘 그리디 문제를 많이 푸는 느낌?

문제에서 주어진 수식에 따르면
Xa + (Xb/2)  또는 Xb + (Xa/2) 두가지 선택을 할 수가 있다. 
최대값을 구하는 것이므로, 더하는 값에 더 큰수가 오게하고, 2로 나누는 값에 작은 수가 오게 하면 greedy하게 풀 수 있다. 

# 에너지드링크

n = int(input())
array = list(map(int, input().split()))
array.sort(reverse=True) # 내림차순 정렬
answer = array[0]

for i in range(1, n):
    answer += array[i]/2

print(answer)
728x90