BOJ 2143 C++

문제접근

처음에는 부 배열의 합이 떨어져있는 합도 가능한줄 알았는데 아니였다.
부 배열의 합은 A[i]+…+A[j]를 의미한다. 이것때문에 시간을 오래잡아 먹었다.
풀이는 간단하다.
배열을 입력받고 전체븨 부 배열의 합을 구한다.
그리고 이분탐색으로 target을 t -arr[index]로 upperbound와 lowerbound를 구해서 빼면 t가되는 경우의 수를 구할 수 있다.

코드

#include <bits/stdc++.h> 
#define ll long long

using namespace std;

int ebun_low(const vector<ll>& s, ll target)
{
	int lo = 0;
	int hi = s.size() - 1;
	while (lo <= hi)
	{
		int mid = (lo + hi) / 2;
		if (s[mid] < target)
			lo = mid + 1;
		else
			hi = mid - 1;
	}
	return lo;
}
int ebun_hi(const vector<ll>& s, ll target)
{
	int lo = 0;
	int hi = s.size() - 1;
	while (lo <= hi)
	{
		int mid = (lo + hi) / 2;
		if (s[mid] <= target)
			lo = mid + 1;
		else
			hi = mid - 1;
	}
	return lo;
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	ll t; cin >> t;
	int a; cin >> a;
	vector<ll> v1(a + 1);
	for (int i = 1; i <= a; i++)
		cin >> v1[i];
	int b; cin >> b;
	vector<ll> v2(b + 1);
	for (int i = 1; i <= b; i++)
		cin >> v2[i];
	vector<ll> s1, s2;
	for (int i = 1; i <= a; i++)
	{
		ll sum = v1[i];
		s1.push_back(sum);
		for (int j = i + 1; j <= a; j++)
		{
			sum += v1[j];
			s1.push_back(sum);
		}
	}
	for (int i = 1; i <= b; i++)
	{
		ll sum = v2[i];
		s2.push_back(sum);
		for (int j = i + 1; j <= b; j++)
		{
			sum += v2[j];
			s2.push_back(sum);
		}
	}
	sort(s1.begin(), s1.end());
	sort(s2.begin(), s2.end());
	ll ans = 0;
	ll size = s1.size();
	for (int i = 0; i < size; i++)
	{
		int hi = ebun_hi(s2, t - s1[i]);
		int lo = ebun_low(s2, t - s1[i]);
		ans += hi - lo;
	}
	cout << ans;
	return 0;
}