[백준 C++] 2143 두 배열의 합 - 이분탐색

2143번: 두 배열의 합

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

int A[1001];
int B[1001];

vector<int> ASum;
vector<int> BSum;

void Init()
{
	int N, M;

	cin >> N;
	for (int i = 0; i < N; ++i)
	{
		cin >> A[i];
	}

	cin >> M;
	for (int i = 0; i < M; ++i)
	{
		cin >> B[i];
	}

	ASum.reserve(N * N);
	for (int i = 0; i < N; ++i)
	{
		int Sum = A[i];
		ASum.emplace_back(Sum);
		for (int j = i + 1; j < N; ++j)
		{
			Sum += A[j];
			ASum.emplace_back(Sum);
		}
	}

	BSum.reserve(M * M);
	for (int i = 0; i < M; ++i)
	{
		int Sum = B[i];
		BSum.emplace_back(Sum);
		for (int j = i + 1; j < M; ++j)
		{
			Sum += B[j];
			BSum.emplace_back(Sum);
		}
	}

	sort(BSum.begin(), BSum.end());
}

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

	int T;
	cin >> T;

	Init();

	long long Cnt = 0;
	for (const int& AS : ASum)
	{
		int FindNum = T - AS;
		vector<int>::iterator Up = upper_bound(BSum.begin(), BSum.end(), FindNum);
		vector<int>::iterator Low = lower_bound(BSum.begin(), BSum.end(), FindNum);
		Cnt += (Up - Low);
	}

	cout << Cnt;
}

---

 

이분 탐색 & 부분합 문제입니다.

풀이 과정은 다음과 같습니다.

 

1. 두 배열의 부분합을 모두 구해서 벡터에 저장

2. B의 부분합 배열을 오름차순 정렬(이분 탐색에 이용)

3. A의 부분합 배열을 처음부터 끝까지 순차적으로 하나씩 선택

4. 선택된 A 부분합과 B의 부분합의 합이 T가 되는 경우를 B의 부분합에 대해서 이분 탐색으로 도출

5. 3~4번 과정을 반복하며 도출된 카운트 값을 모두 합해서 출력