[백준20117/실버1] 호반우 상인의 이상한 품질 계산법 - Python

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

 

처음에 배열을 묶음으로 안묶고 전체 배열의 중앙값 * N이 답인줄알아서 잘못풀었다.

일단 호반우를 묶음으로 묶어서 계산한 후 그 합이 가장 큰 값을 찾아야했다.

먼저 짝수개로 묶었을때 중앙값은 (묶음개수 / 2 + 1) 이 값이므로 묶음 길이를 2로 묶으면 품질을 뻥튀기할 수 있었다.

 

1. 호반우 배열 정렬

2. 가장 끝과 가장 앞을 하나씩 뽑아서 묶은 후 계산하기

3. 이때, (한 묶음의 이익) = (가장 끝 값 * 2)

4. 따라서 배열의 [(N+1)//2:]의 sum * 2 = 전체 이익

5. 배열의 길이가 홀수일 경우 하나 남으므로 더해주기

 

# 성공 코드

N = int(input())
arr = list(map(int, input().split()))
arr.sort()

result = sum(arr[(N+1)//2:]) * 2

if N % 2 == 1:
    result += arr[N//2]

print(result)