두 배열의 합 2143번

배열 두 개 주는데, 각 배열에서 연속된 원소 합 두 개를 더해서 T가 되는 쌍 개수.

예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다.

T(=5) = A[1] + B[1] + B[2]
      = A[1] + A[2] + B[1]
      = A[2] + B[3]
      = A[2] + A[3] + B[1]
      = A[3] + B[1] + B[2]
      = A[3] + A[4] + B[3]
      = A[4] + B[2]

lower_bound(begin, end, val) val 보다 크거나 같은 첫 번째 원소의 주소를 리턴한다. (이상)

upper_bound(begin, end, val) val 보다 큰 첫 번째 원소의 주소를 리턴한다. (초과)

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

const int MAX_N = 1000;

int T;
int N, M;

int AryA[MAX_N];
int AryB[MAX_N];

vector<int> SumA;
vector<int> SumB;

void GetSum()
{
	for (int i = 0; i < N; ++i)
	{
		int Total = 0;
		for (int j = i; j < N; ++j)
		{
			Total += AryA[j];
			SumA.push_back(Total);
		}
	}

	for (int i = 0; i < M; ++i)
	{
		int Total = 0;
		for (int j = i; j < M; ++j)
		{
			Total += AryB[j];
			SumB.push_back(Total);
		}
	}
}

void Input()
{
	cin >> T;
	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> AryA[i];
	}
	cin >> M;
	for (int i = 0; i < M; ++i)
	{
		cin >> AryB[i];
	}
}

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

	Input();
	GetSum();

	sort(SumB.begin(), SumB.end());
	
	long long Answer = 0;
	for (int i = 0; i < SumA.size(); ++i)
	{
		int Num = T - SumA[i];

		Answer += upper_bound(SumB.begin(), SumB.end(), Num) - lower_bound(SumB.begin(), SumB.end(), Num);
	}

	cout << Answer;

	return 0;
}

lower_bound, upper_bound 안 쓰고 풀면

First_Search가 lower_bound

Last_Search가 upper_bound

int First_Search(int* array, int start, int end, int m)
{
	int mid;
	while (start <= end)
	{
		mid = (start + end) / 2;
		
		if (array[mid] < m)
			start = mid + 1;
		else
			end = mid - 1;
	}
	return start;
}

int Last_Search(int* array, int start, int end, int m)
{
	int mid;
	while (start <= end)
	{
		mid = (start + end) / 2;

		if (array[mid] > m)
			end = mid - 1;
		else
			start = mid + 1;
	}
	return start;
}