문제

1번부터 N번까지의 지점이 있다. 각각의 지점들은 차례로, 그리고 원형으로 연결되어 있다. 이 지점들 중 두 곳에 두 개의 탑을 세우려고 하는데, 두 탑의 거리가 최대가 되도록 만들려고 한다.

지점들이 원형으로 연결되어 있기 때문에, 두 지점 사이에는 시계방향과 반시계방향의 두 경로가 존재한다. 두 지점 사이의 거리를 잴 때에는, 이러한 값들 중에서 더 작은 값을 거리로 한다.

연결되어 있는 두 지점 사이의 거리가 주어졌을 때, 두 탑의 거리의 최댓값을 계산하는 프로그램을 작성하시오.

# 2118
import sys
input = lambda: sys.stdin.readline().strip()

# 1. arr
# 2. dist
# 3. binary_search

n = int(input())
arr = [int(input()) for _ in range(n)]

total_dist = sum(arr)

dist = [0] * (n+1)
for i in range(1, n+1):
    dist[i] = dist[i-1] + arr[i-1]
    
max_dist = 0    

def binary_search(start, end, arr, total, first):
    global max_dist
    mid = 0
    while start <= end:
        mid = (start + end) // 2
        dist1 = arr[mid-1] - arr[first-1]
        dist2 = total - dist1
        dist_now = min(dist1, dist2)
        max_dist = max(max_dist, dist_now)
        
        if dist_now == total//2:
            return mid
        elif dist1 < total//2:
            start = mid + 1
        else:
            end = mid - 1
    return mid
    

for i in range(1, n+1):
    binary_search(i, n, dist, total_dist, i)
    
print(max_dist)

백준 2118 두 개의 탑