백준 27651 / CPP / 투포인터 / 이분탐색

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

이 문제는 처음에 조건을 잘못 읽었다 처음에 머리<가슴<배 순인 줄알았지

 

가슴 > 배 , 머리<배 를 만족하는 조건을 찾는 거였다

이에 일단 이문제는 배사이즈를 정해놓고 적절한 머리와 배를 나누는 구간을 찾는 방식으로 문제를 풀어야했다

당연히 배가 머리+가슴 보다 사이즈가 커지게된다면 조건을 만족하게 나눌수 없기에 이부분은 계산 하지 않는다

int binaryHeadBelly(int ED, long long bellyW) {
    if (bellyW >= arr[ED])
        return 0;

    if (ED < 2)
        return 0;

    int st = 1, ed = ED - 1, mid, ans = 0;
    long long S = arr[ED - 1];

    while (st <= ed) {
        mid = (st + ed) / 2;
        if (arr[mid] < bellyW && (S - arr[mid]) > bellyW) {
            ans = mid; 
            st = mid + 1;
        }
        else {
            ed = mid - 1;
        }
    }
    return ans;
}

이 함수를 보자 우리는 bellyW 즉 배의 영역의 총합이랑 머리 가슴 영역의 값을 비교해줄것이다
즉 머리 가슴 영역이 bellyw와 조건을 만족 할 수 있도록 즉 머리가 최대한 크지만 배보다 작게 가슴은 최대한 작지만 배보다 큰 idx를 구한다 이 idx를 ans값이라고 하겠다 이것보다 작은값은 다 정답임으로 경우의 수를 반환한다

전체 코드는 아래와 같다

#include <iostream>
using namespace std;

long long arr[1000000];
int n;

int binaryHeadBelly(int ED, long long bellyW) {
    if (bellyW >= arr[ED])
        return 0;

    if (ED < 2)
        return 0;

    int st = 1, ed = ED - 1, mid, ans = 0;
    long long S = arr[ED - 1];

    while (st <= ed) {
        mid = (st + ed) / 2;
        if (arr[mid] < bellyW && (S - arr[mid]) > bellyW) {
            ans = mid; 
            st = mid + 1;
        }
        else {
            ed = mid - 1;
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    cin >> n;
    arr[0] = 0;
    long long sum = 0, tmp;
    for (int i = 1; i <= n; i++) {
        cin >> tmp;
        sum += tmp;
        arr[i] = sum;
    }

    long long ans = 0;
    for (int i = n; i >= 2; i--) {
        long long bellyW = arr[n] - arr[i - 1];
        ans += binaryHeadBelly(i, bellyW);
    }

    cout << ans;
    return 0;
}