COCI 2014/2015 contest4 3- 조교들의 강의시간(PRIPREME) > 문제은행 : 정보올림피아드&알고리즘




2897 : 조교들의 강의시간(PRIPREME)

제한시간
2000 ms   
메모리제한
32 MB   
해결횟수
18 회   
시도횟수
78 회   

문제

정보올림피아드 전국대회 진출자를 N개의 팀으로 나누어 알고리즘 특강을 하려고 한다. 강사는 우리들의 능력자 근우조교와 범수 조교이다. 두 조교는 각자가 맡은 부분을 모든 팀에게 강의할 예정이다.



당연한 이야기지만 두 조교가 한 팀에게 동시에 강의 할 수 없으며 한 조교가 여러 팀을 한꺼번에 강의하지 않는다. 여러분에게 팀의 수와 각 팀이 알고리즘을 이해하고 구현하는데 걸리는 시간이 주어진다. 이때 근우 조교와 범수 조교가 강의를 모두 마치는데 걸리는 시간의 최소값은 얼마일까?


근우 조교와 범수 조교는 가능한 강의를 빨리 마치고 함께 ACM ICPC 대회 준비를 해야 한다고 한다.

각 팀의 학생들은 전국대회 진출자인 만큼 쉬지 않고 공부할 수 있으며, 우리의 조교들 또한 능력자인 만큼 쉬지 않고 강의 할 수 있을 뿐 아니라 강의실을 이동하는데 추가 시간이 들이 않는다고 한다. ^^


아래 첫 번째 입력 예를 보면 3개의 팀이 있고 각 팀은 알고리즘을 이해하고 구현하는데 2시간씩 걸린다.


한 가지 가능한 방법은 근우 조교가 1팀, 2팀, 3팀 순서로 강의 할 때, 범수조교는 같은 시간에 3팀, 1팀 2팀 순으로 강의하면 6시간이면 모든 강의가 끝난다.


두 번째 입력 예의 경우에는 근우 조교가 2팀, 3팀 순으로 강의 한 후 1시간 쉬고 1팀에게 강의 할 때, 범수조교는 1팀, 2팀, 3팀 순으로 강의한 후 1시간 쉬면서 근우 조교가 강의를 마치는 것을 기다린다.


따라서 두 조교가 모든 강의를 마치는데 걸리는 시간은 8시간이다.

입력형식

첫 행에 팀 수 N( 1 ≤ N ≤ 300,000) 입력된다. 두 번째 행에 각 팀이 알고리즘을 이해하고 구현하는데 걸리는 시간 Ti ( 1≤ Ti ≤ 300,000)이 공백으로 구분하여 주어진다. 입력 데이터의 40%는 N ≤ 7 이다.

출력형식

두 조교가 모든 강의를 끝내는데 걸리는 최소시간을 출력한다.

입력 예

3
2 2 2

출력 예

6

입력 예

3
4 1 2

출력 예

8

입력 예

4
1 3 2 1

출력 예

7


경기도 안양시 동안구 평촌대로 109 협성골드프라자 601호

TEL : 031-360-4144 FAX : 031-388-0996 E-mail : hancomc@hotmail.com, comkiwer@naver.com

Copyrightⓒ 2010 jungol. All right reserved.

TOP