[Java] 백준 23032번 : 서프라이즈~

문제

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

 

접근 방법

1. 브루트포스로 문제를 풀 게 된다면 시간초과가 발생할 것이다.
2. 따라서 누적합과 투포인터를 섞어서 문제를 풀었다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    private static BufferedReader br;
    private static StringBuilder sb;
    private static StringTokenizer st;
    private static int N;
    private static int[]arr;
    private static int[]prefix;
    private static int min,answer;

    //입력
    public static void input() throws Exception{
        br = new BufferedReader(new InputStreamReader(System.in));
        sb = new StringBuilder();

        N = Integer.parseInt(br.readLine());
        arr = new int[N+1];
        prefix = new int[N+1];

        st = new StringTokenizer(br.readLine());
        for(int i = 1 ; i <= N ; i++){
            arr[i] = Integer.parseInt(st.nextToken());
            //누적합
            prefix[i] = prefix[i-1]+arr[i];
        }

    }

    //과정
    public static void process(){
        min = Integer.MAX_VALUE;
        answer = 0;

        for(int i = 1 ; i <= N ; i++){
            int s = i;
            int e = i+1;

            while(s>0 && e <=N){
                //i로 해주는 이유는 왼쪽과 오른쪽 범위를 잘 나누어 주어야 하기 때문이다.
                int left = prefix[i]-prefix[s-1];
                int right = prefix[e] - prefix[i];

                if(min> Math.abs(right-left)){

                    min = Math.abs(right-left);
                    answer = prefix[e]-prefix[s-1];
                }
                else if(min == Math.abs(right-left)){
                    answer = Math.max(answer, prefix[e] - prefix[s-1]);
                }

                if(left>=right){
                    e++;
                }else{
                    s--;
                }
            }
        }
        System.out.println(answer);
    }

    public static void main(String[] args) throws Exception{
        input();
        process();
    }
}