[백준 2118] 두 개의 탑 - JAVA

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

 

누적 합 + 투 포인터

 

시계 방향이 반시계 방향보다 짧은 거리일 동안

답을 시계 방향과 비교한다.

 

다음 포인터는 반시계 방향이 시계 방향보다 짧은 거리임이 보장되므로

답을 반시계 방향과 비교한다.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;


public class Main {

  static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

  static int N, total, ans;
  static int[] sum;

  public static void main(String args[]) throws IOException {
    N = Integer.parseInt(br.readLine());
    sum = new int[N];
    sum[0] = Integer.parseInt(br.readLine());

    for (int i = 1; i < N; i++) {
      sum[i] = sum[i - 1] + Integer.parseInt(br.readLine());
    }

    total = sum[N - 1];

    int r = 1;
    for (int l = 0; l < N; l++) {

      while (r < N && sum[r] - sum[l] < total - (sum[r] - sum[l])) {
        ans = Math.max(ans, sum[r] - sum[l]);
        r++;
      }

      if (r < N) {
        ans = Math.max(ans, total - (sum[r] - sum[l]));
      }
    }

    System.out.println(ans);
  }
}