[백준 20115] 에너지드링크(Python)

1. 문제출처

백준 20115: 에너지드링크

2. 문제분석

2.1 문제해석

모든 음료수를 합칠 때 최대의 양이 될 수 있도록 해야한다.
즉, 음료수를 흘리는 양을 최소한으로 만들어야 한다.

2.2 접근법

음료수의 양을 리스트로 받은 다음 정렬을 했다.

음료수의 양은 다음의 식으로 계산한다.

즉, 재료 1의 양은 유지되는 반면에 재료 2의 양은 조제 때마다 절반으로 줄어든다.
줄어드는 양을 줄이기 위해서는 재료2의 양을 최소 양의 음료수를 넣어야한다.

정렬된 리스트의 첫번째 원소부터 마지막 앞까지만 순회하면서 끝의 최대값을 위의 계산식으로 계속 갱신하였다. 끝까지 순회한 후 갱신 된 최대값을 반환하면 된다.

3. 나의 코드

# 2024.05.22(수)
# 백준 20115: 에너지 드링크 https://www.acmicpc.net/problem/20115
# 주제: 그리디 알고리즘

import sys

input = sys.stdin.readline


def sol():
    print(logic(inputs()))


# 입력값 받기
def inputs():
    N = int(input())
    drinks = [x for x in map(int, input().split())]

    return N, drinks


# 로직: 에너지 드링크 만들기
def logic(N, drinks):
    drinks.sort()  # 에너지 드링크 조제를 위해 정렬

    for i in range(N - 1):  # 처음부터 최대값전까지 순회하면서 에너지 드링크 조제
        drinks[-1] = drinks[-1] + drinks[i] / 2  # 최대값에 갱신

    return drinks[-1] # 최대값 반환


sol()

4. 배운 점

처음에는 힙큐를 이용해서 풀려고 했는데 시간초과가 났다. 힙큐에서 값을 추가, 삭제하면 정렬에 시간이 필요하는데 이 부분이 시간초과를 일으킨 것 같았다.
별도로 정렬하지 않고 맨 끝의 최대값만 갱신하면 리스트는 정렬구조를 유지할 수 있다. 그리고 조제할 수 있는 음료수 최대 양을 구하는 것이기 때문에 맨 끝의 값만 갱신하면 되었다.

5. 총 정리

• 너무 복잡하게 생각하지 말기
• 시간복잡도를 고려해서 로직 짜기