[백준] 27651 - 벌레컷

[문제]

---

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

[풀이]

---

머리 가슴 배를 오름차순으로 정렬하면, 머리 배 가슴 순으로 되도록 해야한다.
머리와 가슴을 f를 기준으로 나누고, 가슴과 배를 조건에 맞게 이분탐색으로 나누어 준다.

1. 머리와 배를 나누어 준다.
2. 가슴과 배를 나누어 준다.
3. 1과 2의 기준 값의 차이가 경우의 수이고 이를 기록해둔다.

[코드]

---

def solve(n,a):
	ans=0
	s=[a[0]]
	for i in range(1,n):
		s.append(s[i-1]+a[i])
	
	f=0
	blo=f+1
	bhi=n-2
	while 1:
		lo=blo-1
		hi=bhi+1
		while lo+1<hi:
			mid=(lo+hi)//2
			if s[-1]-s[mid]>s[f]: lo=mid
			else: hi=mid
		if lo==blo-1: return ans
		bhi=lo
		
		lo=blo-1
		hi=bhi+1
		while lo+1<hi:
			mid=(lo+hi)//2
			if s[mid]-s[f]>s[-1]-s[mid]: hi=mid
			else: lo=mid
		if hi==bhi+1: return ans
		blo=hi
		
		if blo>bhi: return ans
		ans+= bhi-blo+1
		f+=1
		
n=int(input())
a=list(map(int, input().split()))
print(solve(n,a))