백준_20115 (에너지 드링크_실버3_그리디)

• 링크 : https://www.acmicpc.net/problem/20115

---

메모

메모한 것

1. "임의" 두 개 골라
2. A -> B 이동 (A의 절반만 이동, 나머지버림)
3. A 버림
4. 에너지 드링크 하나 남을 때까지 1~3 반복

합쳐진 에너지 드링크 양을 최대로 하고싶음
-> 앞에서부터 비교해서 더 적은 애를 이동시키면 될듯

이때 큰순이나 작은 순으로 정렬하면 손해임

일단 while문 돌려야 하고

큰 순으로 정렬한 다음에 양 끝쪽에서 각각 하나씩 꺼내서 큰<-작은 옮기면 되겠다

알고리즘

arr 입력받고
sort()
while len(arr) > 1:
    arr[0] += (arr[-1] * 0.5)
    arr.pop()

---

솔루션 코드 - 내가짠 (10분컷)

• 어차피 가장 큰 비커에 다 넣을거기 때문에
  • 정렬 후
  • 가장 큰 비커에 브루트포스로 넣어주면서 쓴건 pop해서 버려버림

import sys
n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))

arr.sort(reverse=True)

while len(arr) > 1:
    # 0번째가 제일 큰 것임, 브루트포스할수밖에 없음
    arr[0] += (arr[-1] * 0.5)
    arr.pop()
    
print(arr[0])

---

솔루션 코드 - 내가짠 -> 연산량 줄임

• 쓸데없이 pop()할 필요가 없었다
• 위 코드랑 동일하나, 버린다의 개념에 목메이지 않아도 되었음

import sys
n = int(sys.stdin.readline())
arr = list(map(int,sys.stdin.readline().split()))

arr.sort()
for i in range(n-1):
    arr[n-1] += (arr[i] * 0.5)      # n번째가 제일 큰 녀석임
    
print(arr[-1])