[백준/BOJ] 백준 27651번 : 벌레컷

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

27651번: 벌레컷

 

무게의 조건이 가슴 > 배 > 머리 이므로, 이를 가슴 > 머리, 배 > 머리, 가슴 > 배로 나눠서 생각했다.

전체적인 풀이 방법은, 1~x까지 머리 부위, x+1~y까지 가슴 부위, y+1~n까지 배 부위로 나눠서 모든 x를 확인해 보면서, 해당 x에 대해, 가슴 > 머리, 배 > 머리 를 만족하는 y가 될 수 있는 후보 범위 (range_y_left~range_y_right)를 구했고, y가 될 수 있는 후보 범위에서 가슴 > 배를 만족하는 가장 작은 y(min_y)를 이분탐색으로 구해서, 해당 x에서 만들어질 수 있는 y의 개수(range_y_right - min_y + 1)를 구하는 방법으로 문제를 해결했다.

 

코드

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;

int n;
vector<long long> a(1000005, 0);
vector<long long> psum(1000005, 0);
long long result = 0;

// 위치 순서 : 머리, 가슴, 배
// 무게 : 가슴 > 배 > 머리 -> 해당 조건은 가슴 > 머리, 배 > 머리, 가슴 > 배 로 나눠서 생각

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

	cin >> n;

	for (int i = 1; i <= n; i++) {
		long long input;
		cin >> input;

		a[i] = input;
		psum[i] = psum[i - 1] + a[i];
	}

	int range_y_left = 2;
	int range_y_right = n - 1;
	for (int i = 1; i < n; i++) {

		int x = i; //([1~x] 까지 머리 부위
		range_y_left = max(x + 1, range_y_left);

		//y가 될 수 있는 범위를 구한다
		// 머리 크기는 정해졌으므로, 머리 크기를 기반으로, 가슴>머리, 배>머리 를 만족하는 범위를 구한다

		//가슴 > 머리가 되도록 한다
		while (psum[range_y_left] - psum[x] <= psum[x]) {
			range_y_left++; //가슴 부위의 크기를 늘린다

			if (range_y_left >= n) {
				break;
			}
		}

		//배 > 머리가 되도록 한다
		while (psum[n] - psum[range_y_right] <= psum[x]) {
			range_y_right--; //배 부위의 크기를 늘린다

			if (range_y_right <= x) {
				break;
			}
		}

		//가슴>머리, 배>머리를 만족하는 경우 자체가 없을때
		//이후의 머리 범위도 다 만족할 수 없다
		if (range_y_left >= n || range_y_right <= x || range_y_left > range_y_right) {
			break;
		}

		// range_y_left ~ range_y_right 에서 가슴 > 배 를 만족하는 위치 중 가장 작은 위치를 이분 탐색을 통해 찾는다
		int left = range_y_left;
		int right = range_y_right;
		int min_y = -1;
		while (left <= right) {
			int mid = (left + right) / 2; //mid를 y라고 생각하는 경우
			//가슴 > 배 를 만족할때
			if (psum[mid] - psum[x] > psum[n] - psum[mid]) {
				min_y = mid;
				right = mid - 1;
			}

			//가슴 <= 배 일때
			//가슴 부위의 크기를 늘린다
			else {
				left = mid + 1;
			}
		}

		//x가 i일때, 조건을 만족하는 y가 없을때
		if (min_y == -1) {
			continue;
		}

		//x가 i일때, 조건을 만족하는 가장 작은 y가 min_y일때
		result += (long long)(range_y_right - min_y + 1);
	}

	cout << result << "\n";

	return 0;
}