[백준/Python] #20115 : 에너지드링크 - 그리디

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

20115번: 에너지 드링크

 

 

'합쳐진 에너지 드링크의 양을 최대로 하려 한다 = 반으로 버려지는 에너지 드링크의 양은 최대한 적어야 한다'

이므로 일단 가장 큰 값은 반이 버려져서는 안된다.

 

드링크a, 드링크b를 합칠 때 식으로는 xa + (xb / 2) 와 같이 표현할 수 있으므로,

가장 양이 많은 드링크에 나머지 드링크의 반을 모두 하나씩 더해주며 결과값을 갱신하면 된다.

 

---

처음에는 약간 잘못 생각해서 오름차순으로 정렬한 뒤, 가장 작은 드링크의 반을 그 다음으로 적은 드링크에 더하고, 더해진 값을 다시 반으로 나눠서 다음 인덱스의 드링크에 더하고, 이런식으로 갱신되도록 코드를 짰었는데,

직접 계산해봐도 출력값이 달라서 다른 풀이들을 찾아보다가

다들 내림차순으로 풀길래 보다가 내가 아이디어는 곧잘 떠올렸는데 구현 과정에서 잘못 생각하고 있었다는 걸 깨달았다.

 

그리고 다시 푼 제대로 된 풀이

n = int(input())    # 3 2 10 9 6
drink_list = list(map(int, input().split()))
drink_list.sort(reverse=True)   # 10 9 6 3 2

result = drink_list[0]
for i in range(1, n):
    result += drink_list[i] / 2

print(result)

 

정렬 시 sort(reverse=True)처럼 해주면 오름차순 정렬의 순서를 반대로 바꾸어 내림차순으로 정렬해줄 수 있다.

 

 

+)

처음에 내가 오름차순으로 풀었다가 (오름차순으로 푼) 다른 풀이들이랑 비교해서 잘못 푼 걸 알게 된거였어서

근데 오른차순으로 풀면 안되나? 왜 대부분 내림으로 풀었지 하는 생각에

내림차순으로도 풀어봤다...

n = int(input())    # 3 2 10 9 6
drink_list = list(map(int, input().split()))
drink_list.sort()   # 2 3 6 9 10

result = drink_list[n - 1]
for i in range(n - 1):
    result += drink_list[i] / 2

print(result)

예상되는 부분이긴 한데 별로 다를 건 없음 솔직히

다만 아주 미세하게 내림차순 풀이가 조금 더 깔끔하다고 해야되나