[C++] 백준 27651번: 벌레컷 - Binary Search

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

27651번: 벌레컷

---

주어진 수열을 3분할하는데, 이를 각각 머리, 가슴, 배라고 지칭한다.

1 ~ x 의 크기 < y + 1 ~ n의 크기 < x + 1 ~ y 를 만족하는 수열의 개수를 구해야한다.

즉, 머리 < 배 < 가슴을 만족해야한다.

이를 위해 우선 1 ~ n까지의 수열의 합을 배열에 저장해주어 중복으로 덧셈을 실시하는 일이 발생하지 않도록 누적합을 이용했다.

 

먼저 1 ~ x를 구하는 것은 간단하다. 단순히 for문을 돌려 1 ~ i번째를 지정해주면 바로 머리의 크기이다.

이제 중요한 것은 가슴 > 배를 만족함과 동시에 배 > 머리를 만족해야한다.

 

이를 위해 먼저 배 > 머리를 만족하는 가장 큰 인덱스를 구했다.

해당 인덱스보다 작은 인덱스라면 무조건 배 > 머리를 만족할 것이고, 인덱스를 줄여가며 가슴 > 배를 만족하는 가장 작은 인덱스를 구하도록 접근했다.

우선 배 > 머리를 만족하는 가장 큰 인덱스를 구했고, 가슴 > 배를 만족하는 것은 당연히 가슴 > 머리를 만족할 것이다.

최종적으로 배 > 머리를 만족하는 인덱스 - 가슴 > 배를 만족하는 인덱스를 해주면 원하는 수열의 개수가 나올 것이다.

 

#include <iostream>
using namespace std;
using ll=long long;
ll dp[1000001], sum[1000001];
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    ll n, h, ans=0; cin >> n;
    for(int i=1; i<=n; i++){
        cin >> dp[i];
        sum[i]+=sum[i-1]+dp[i];
    }
    for(int i=1; i<n-1; i++){
        h=sum[i];
        ll f=i+1, e=n-1, m, idx;
        m=(f+e)/2;
        while(f<=e){
            if(sum[n]-sum[m]>h) f=m+1;
            else e=m-1;
            m=(f+e)/2;
        }
        if(sum[m]-sum[i]<=sum[n]-sum[m]) continue;
        idx=m;
        f=i+1, e=n-1;
        while(f<=e){
            if(sum[m]-sum[i]>sum[n]-sum[m]) e=m-1;
            else f=m+1;
            m=(f+e)/2;
        }
        ans+=idx-m;
    }
    cout << ans;
}