https://www.acmicpc.net/problem/20115
코드
n = int(input())
drinks = list(map(int, input().split()))
drinks.sort()
ans = drinks[-1]
for i in range(len(drinks)-1):
ans += (drinks[i]/2)
print(ans)
처음에는 남은 음료들 중 가장 양이 적은 2개를 골라서 합쳐야 하는줄 알았는데, 아니었다. 매 순서에 2로 나누어지는 음료들을 최대한 작게 해주어야 하는데, 이렇게 하면 그럴 수 없다.
예를 들어, 음료 5개가 가장 작은 것부터 순서대로 a, b, c, d, e 이렇게 있다고 하면 원래 생각한 방법대로면 처음에 a, b를 뽑아서 (a/2)+b를 만들게 된다. 그 다음 순서에 2개를 뽑으면 c와 d 또는 c와 (a/2)+b를 뽑게 되는데, 처음에 가장 작은 a와 b보다 양이 많은 다른 음료수를 골랐다면 2번째에 2로 나누어질 음료는 b를 고를 수 있었다. 그러니까 2개를 고를 때 가장 작은 2개가 아닌, 가장 작은 1개와 가장 큰 1개를 골라야 하는 것이다.
그래서 입력을 받은 음료들을 크기 오름차순으로 정렬하고 앞의 n-1개의 음료들을 절반 나눈 값과 마지막 음료의 합을 구하도록 코드를 수정했다.
'문제풀이 > Greedy' 카테고리의 다른 글
[Python/파이썬] 백준 1911번 흙길 보수하기 (0) | 2024.06.04 |
---|---|
[Python/파이썬] 백준 2012번 등수 매기기 (0) | 2024.05.27 |
[Python/파이썬] 백준 17451번 평행 우주 (0) | 2024.05.03 |
[Python/파이썬] 백준 19598번 최소 회의실 개수 (0) | 2024.05.02 |
[Python/파이썬] 백준 11501번 주식 (0) | 2024.03.18 |