[백준/BOJ] 백준 2143번 : 두 배열의 합

www.acmicpc.net/problem/2143

2143번: 두 배열의 합

두 배열의 누적합을 구한 뒤 이를 통해 두 배열의 각각 부 배열의 합 구한다 그리고 이것을 정렬한 뒤 배열 a의 부 배열의 합 값을 모두 확인하며 해당 값과 더해서 t가 되는 것의 개수를 b의 부 배열의 합에서 lower_bound와 upper_bound를 통해 구하는 방식으로  문제를 해결했다.

 

코드

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

int t;
int n;
vector<int> a;
int m;
vector<int> b;

vector<int> a_psum; //a의 누적합
vector<int> b_psum; //b의 누적합

vector<int> a_bsum; //a 부 배열의 합
vector<int> b_bsum; //b 부 배열의 합

vector<int>::iterator it1;
vector<int>::iterator it2;

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

	cin >> t;

	cin >> n;

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

		a.push_back(input);
	}

	cin >> m;

	for (int i = 0; i < m; i++)
	{
		int input;
		cin >> input;

		b.push_back(input);
	}

	//a의 누적합 계산
	a_psum.push_back(a[0]);
	for (int i = 1; i < n; i++)
		a_psum.push_back(a_psum[i - 1] + a[i]);

	//b의 누적합 계산
	b_psum.push_back(b[0]);
	for (int i = 1; i < m; i++)
		b_psum.push_back(b_psum[i - 1] + b[i]);

	//a의 모든 부 배열합 계산
	for (int i = 0; i < n; i++)
	{
		a_bsum.push_back(a_psum[i]);
		for (int j = 0; j < i; j++)
			a_bsum.push_back(a_psum[i] - a_psum[j]);
	}

	//b의 모든 부 배열합 계산
	for (int i = 0; i < m; i++)
	{
		b_bsum.push_back(b_psum[i]);
		for (int j = 0; j < i; j++)
			b_bsum.push_back(b_psum[i] - b_psum[j]);
	}

	//정렬
	sort(a_bsum.begin(), a_bsum.end());
	sort(b_bsum.begin(), b_bsum.end());

	long long result = 0;
	for (int i = 0; i < a_bsum.size(); i++)
	{
		int find_num = t - a_bsum[i]; //찾을 숫자

		it1 = lower_bound(b_bsum.begin(), b_bsum.end(), find_num);

		if (it1 != b_bsum.end() && *it1 == find_num) //찾았을때
		{
			it2 = upper_bound(b_bsum.begin(), b_bsum.end(), find_num);

			result += it2 - it1;
		}
	}

	cout << result;

	return 0;
}