백준 2118번: 두 개의 탑

문제 설명

• https://www.acmicpc.net/problem/2118
• 원형으로 연결된 점들 사이에서 거리가 가장 먼 두 점 사이의 거리를 구하는 문제입니다.
  • 두 점 사이의 거리는 시계방향 연결과 반시계방향 연결 중 더 작은값을 기준으로 합니다.

접근법

• 두 점 사이의 거리를 빠르게 계산하기 위해 누적합을 사용합니다.
  • 시계방향으로의 연결이 반시계방향 연결보다 더 커지면 더이상 확인할 필요가 없습니다.

정답

	import java.util.*;
	import java.io.*;
	
	public class Main {
		public static void main(String[] args) throws IOException {
			BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
			int N = Integer.parseInt(br.readLine());
			int[] arr = new int[N+1];
			for (int i = 1; i <= N; i++) {
				arr[i] = Integer.parseInt(br.readLine())+arr[i-1];
			}
			int maxVal = Integer.MIN_VALUE;
			for (int a = 1; a <= N; a++) {
				for (int b = a; b <= N; b++) {
					int RightDistance = arr[b-1]-arr[a-1];
					int LeftDistance = arr[N]-RightDistance;
					int D = Math.min(RightDistance,LeftDistance);
					maxVal = Math.max(maxVal, D);
					if(RightDistance>=LeftDistance) break;
				}
			}
			System.out.println(maxVal);
		}
		
		
	}