[BOJ] 2143 두 배열의 합

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

2143번: 두 배열의 합

알고리즘: 투포인터

 

시간복잡도: $O(N^2logN^2)$

---

접근:

1. 부 배열은 연속적이다.

2. A 부 배열의 합 + B 부 배열의 합 = T를 만족하는 가짓수 구하기

   (합 + 합 = T 가짓수 구하기)

 

->

2번 조건을 보면 이 문제는 투포인터 문제라는 것을 알 수 있다.

다만 기본적인 투포인터 문제에서 1번 조건의 부 배열이라는 요소만 추가되었는데,

여기서 부 배열이 연속적이라는 것만 캐치해내면 된다.

 

부 배열이 연속적이기 때문에 연속합을 구하는 DP 문제처럼

i~j 까지의 구간합을 다 구해서 새로운 배열에 넣어주면 된다.

여기서 $O(N^2)$의 시간복잡도가 걸리고,

투포인터를 사용하기 위해 정렬을 하기 때문에 최종 시간복잡도는, $O(N^2logN^2)$

 

// 2143: 두 배열의 합
#include<iostream>
#include<algorithm>
using namespace std;

int T, n, m, la, lb, st, en;
int in[1001], a[1001*1001], b[1001*1001];
long long int ans, na, nb;
int main()
{
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	
	cin >> T >> n;
	for (int i = 1; i <= n; ++i)
	{
		cin >> in[i];
		in[i] += in[i-1];
	}
	for (int i = 1; i <= n; ++i)
		for (int j = i; j <= n; ++j)
			a[la++] = in[j] - in[i-1];
	
	cin >> m;
	for (int i = 1; i <= m; ++i)
	{
		cin >> in[i];
		in[i] += in[i-1];
	}
	for (int i = 1; i <= m; ++i)
		for (int j = i; j <= m; ++j)
			b[lb++] = in[j] - in[i-1];
	
	sort(a, a+la);
	sort(b, b+lb);
	
	en = lb-1;
	
	while (st < la && en >= 0)
	{
		int sum = a[st] + b[en];
		
		if (sum == T)
		{
			na = 1, nb = 1;
			st++, en--;
			while (a[st-1] == a[st] && st < la){ st++, na++; }
			while (b[en+1] == b[en] && en >= 0){ en--, nb++; }
			ans += na * nb;
		}
		else if (sum < T)
			st++;
		else
			en--;
	}
	
	cout << ans;
	return 0;
}