[ BOJ ] 24755 : Election Paradox ( SILVER 5 ) / Python

문제

In Oddland, the leader of the country is determined by a democratic election.  The country is divided into an odd number of regions, in which each region has an odd number of voters.

There are two (an even number!) political parties in Oddland, and the winning party is the one that wins the most number of regions.  A party wins a region if it receives more votes than the other party in that region.

Under this system, it is possible that the losing party receives more votes than the winning party.  For example, if there are three regions with 11, 3, and 3 people, respectively, then a party could receive 8, 1, and 1 votes and lose the election.  In this case, the losing party received the majority of the votes in the total population.

Determine the largest number of votes a party can receive and still lose the election.

입력

The first line of input contains an odd integer N (3≤N≤999), which is the number of regions in Oddland. 

The next line contains N odd integers p[i] (1≤p[i]≤999), which are the populations of the N cities.

출력

Display the largest number of votes a party can receive and still lose the election.

풀이 과정

절반 정도의 도시는 전체 득표를 받고, 나머지 도시는 과반수 미만의 표를 받는데, 전체 득표를 받는 도시는 정렬을 이용해 가장 유권자가 많은 도시를 고른다. 그리디하게 풀 수 있는 문제이다.

import sys
input = sys.stdin.readline

n = int(input())
arr = list(map(int, input().split()))

arr.sort(reverse=True)

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

print(result)