[백준] 25635번 자유 이용권 (gold 4

import java.io.*;
import java.util.*;

public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br=new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw=new BufferedWriter(new OutputStreamWriter(System.out));
        int n=Integer.valueOf(br.readLine());

        long total=0;
        int[] num=new int[n];
        StringTokenizer st=new StringTokenizer(br.readLine());
        for(int i=0; i<n; i++) {
            int t = Integer.valueOf(st.nextToken());
            num[i] = t;
            total += t;
        }

		//풀이. 케이스들을 살펴보니, 사실 연속하지 않게 나열하는 것은,
        //어떤 A가있을때, 만약 이미 깔린게 A이상 혹은 A이면 그안에 어떻게 잘 흩뿌리면
        //무조건 연속하지 않게 나열이 가능하다.
        //따라서 총 갯수를 더해서, 작은 케이스들부터 비교한다.
        //이때 비교하면서 더할때, 총합의 갯수보다 작거나 같으면 무조건 다 포함하는데 
        //그 이유는, 그 수를 다 쓰더라도 뒤에서 그 이상만큼의 놀이기구 이용수가 나오는게
        //보장되어 있기 때문이다. 따라서 다음과 같이 케이스를 다 돌리고,
        //마지막 경우 즉, 가장 큰 경우에서는 지금까지 나열된 배열의 크기와 비교하여 판단한다.
        long answer=0;
        for(int i=0; i<n-1; i++){
            int temp=num[i];
            if(temp<=total){
                answer+=temp;
            }
            total-=temp;
        }

        if(num[n-1]<=answer){
            answer+=num[n-1];
        }
        else{
            answer+=answer+1;
        }
        bw.write(answer+"");
        bw.flush();
    }
}