[백준] 20115번 에너지 드링크 (파이썬)

 

문제

 

20115번: 에너지 드링크

 

풀이 (Python)

 

#많은 양을 남기고 적은양을 /2값하여 많은 에너지 드링크에 합치면 되는 문제

n=int(input())
arr=list(map(int,input().split()))


max_drink=max(arr)
arr.remove(max_drink)   #제일 큰 값 제외 전부 /2하여 큰값에 더하면 되기 때문에 

for ele in arr:         #for문을 통해 제일 큰 값에 계속 더해주기
    max_drink+=ele/2

print(max_drink)

 

설명  (Python)

 

에너지 드링크 문제는 그리디 알고리즘 문제로써 문제를 이해하면 거의 백준 기준 브론즈급 문제이다.

문제가 굉장히 길게 설명되어 있는데  다른 음료수를 다른 음료수 통에 넣을 때 /2 하여 넣고 버리는 문제이다.

 

어떻게 하면 가장 많은 양을 남길 수 있을까?

 

음료를 합치는 경우에 한 개의 음료수는 /2되고 나머지 음료수는 그대로 합쳐지기 때문에 더 큰 음료수가 그대로 남아야 하고, 더 적은 음료수가 /2되어야 한다.

 

이때 음료수가 a, b, c 3개가 있고 음료량은 a <b <c라 가정할 때

a와 b음료를 합치는 경우에 a음료를 /2 하여 b에 더해준다. (b=b+a/2)

 

b음료와 c음료를 합칠 때는 b음료를 /2 하여 c에 더해준다.(c=c+b/2)

 

∴ 제일 큰 음료에 나머지 음료 모두를 /2 하여 더해주면 된다.

 

 

 

max_drink=max(arr)
arr.remove(max_drink)   #제일 큰 값 제외 전부 /2하여 큰값에 더하면 되기 때문에 

for ele in arr:         #for문을 통해 제일 큰 값에 계속 더해주기
    max_drink+=ele/2

위의 코드와 같이 제일 큰 음료를 max_drink에 저장 후 리스트에서 제거하고,

나머지 원소들을 /2 하여 max_drink에 더해주면 된다.