백준 온라인 저지, 자료구조 / 15577번: Prosjek (파이썬 / , 백준 실버문제)

문제

Little Ivica received N math grades and wants to calculate their average. He knows that the average of two numbers a and b is calculated as (a + b) / 2, but he still doesn’t know how to do it for multiple numbers. He calculates the average by writing down N grades and repeating the following operations N - 1 times:

1. He chooses two numbers and erases them.
2. He writes down the average of the two chosen numbers.

After precisely N - 1 steps, the only number written down will be the one representing the average grade to Ivica. It is your task to determine the largest average that can be obtained this way.

입력

The first line of input contains the integer N (1 ≤ N ≤ 20), the number from the task.

The i^th of the following N lines contains the integer X_i (1 ≤ X_i ≤ 5), the i^th grade.

출력

Output the largest possible average from the task. Your solution is allowed to deviate from the official one for 0.000001.

제한

예제 입력 1

4
2
4
5
2

예제 출력 1

4.000000

예제 입력 2

3
5
5
4

예제 출력 2

4.750000

예제 입력 3

3
1
3
5

예제 출력 3

3.500000

힌트

Clarification of the third test case:

Initially, the numbers 1, 3 and 5 are written down.

In the first step, Ivica chooses numbers 1 and 3, erases them and writes down 2. After the first step, 2 and 5 are written down.

In the second step, Ivica chooses the remaining two numbers which average is 3.5.

접근 방법

- 작은 숫자 두개를 선택해 두 숫자의 평균을 저장한 뒤, 이를 우선순위 큐에 저장한다.
- 출력은 소수점 6자리까지 출력한다.

코드

# https://www.acmicpc.net/problem/15577
# 접근 방법
# 작은 숫자 두개를 선택해 두 숫자의 평균을 저장한 뒤, 이를 우선순위 큐에 저장한다.
# 출력은 소수점 6자리까지 출력한다.
import heapq
n = int(input())
h = []
for _ in range(n):
    heapq.heappush(h, int(input()))

for _ in range(n-1):
    x1 = heapq.heappop(h)
    x2 = heapq.heappop(h)
    heapq.heappush(h, (x1+x2) / 2)
print('{:.6f}'.format(h[0]))