원주민

면접 대비

시간 제한1초메모리 제한512 MB

요약

보물 n개의 가치가 주어질 때, 추장에게 절반 이상을 준 뒤 캡틴이 가질 수 있는 최대 가치의 합을 구합니다.

문제

탐험가 쿡 선장과 그의 팀이 섬 원주민에게 붙잡혔습니다. 잡아먹히지 않으려면 모험가들이 보물 일부를 원주민에게 줘야 합니다. 선장에게는 $n$ 개의 보물이 있습니다.

추장은 보물의 절반 이상을 받으면 선장과 팀을 풀어주기로 합니다. 추장은 어떤 보물을 받을지는 신경 쓰지 않고, 보물을 절반 이상 받기만을 원합니다.

각 보물의 가치는 쿡만 알고 있습니다. $i$ 번째 보물의 가치는 $a_i$ 입니다. 선장이 자기가 가질 보물의 가치 합이 최대가 되도록, 추장에게 줄 보물을 정하도록 도와주세요.

첫째 줄에 정수 $n$ ( $2 \le n \le 1000$ )이 주어집니다.

둘째 줄에 정수 $a_1, a_2, \ldots, a_n$ ( $1 \le a_i \le 1000$ )이 주어집니다.

선장이 원주민에게 보물을 절반 이상 준 뒤 자기가 가질 수 있는 보물 가치 합의 최댓값을 정수 하나로 출력합니다.