[백준][누적합][이분탐색] 2118. 두 개의 탑

2118. 두 개의 탑

 

 

• 내 풀이
  • 누적합 + 이분탐색
    • 수열을 2배로 확장해 원형 구조를 선형처럼 처리
    • 누적합 배열을 만들어 i ~ n+i 구간으로 슬라이싱
    • 각 구간에 대해 구간의 총합의 절반(mid)을 기준으로 bisect로 균등 분할 위치 탐색
      • 가장 비슷하게 나뉠 때 = |앞합 - 뒷합|이 최소
      • bisect으로 나오는 위치는 중간값에 가까운 값이지 정확히 |앞합 - 뒷합| 이 최소가 되는 값은 X
        • 그렇기 때문에 bisect 의 idx와 idx-1 위치의 값을 모두 비교해봐야함
    • min(좌합, 우합) 값 들 중에 가장 max인 값

from bisect import bisect_left

n = int(input())
nums = [0]+list(int(input()) for _ in range(n))

prefix_sum = [0 for _ in range(2*n)]
for i in range(1, n+1):
    prefix_sum[i] = prefix_sum[i-1]+nums[i % (n+1)]
for i in range(n+1, 2*n):
    prefix_sum[i] = prefix_sum[i-1]+nums[i % n]

answer = 0
for i in range(1, n):
    tmp = prefix_sum[i:n+i+1]
    mid = (tmp[0]+tmp[-1])//2
    idx = bisect_left(tmp, mid)

    x = tmp[idx]-tmp[0]
    y = tmp[-1]-tmp[idx]

    a = tmp[idx-1]-tmp[0]
    b = tmp[-1]-tmp[idx-1]

    if abs(x-y) < abs(a-b):
        answer = max(answer, min(x, y))
    else:
        answer = max(answer, min(a, b))


print(answer)