BOJ : 2143 두 배열의 합

---

[BOJ 2143(G3)리뷰]

투 포인터를 응용해야 하는 문제이다.

문제에서 배열이 두개가 주어지고, 두개의 배열을 이용하여 만들 수 있는 합 중 T를 만족하는 경우의 수를 찾아야 한다.

완전탐색하는 방법으로는 시간초과를 맞게 되므로 투포인터 알고리즘을 이용해야 한다. 

투 포인터 알고리즘을 이용하기 위하여 A와 B배열에 대해 각각의 구간합을 저장하는 사전작업을 했다.
즉, 1,3,2,1 배열이라면 1 4 6 7 3 5 6 2 3 1 라는 별도의 배열을 만든다.

그리고 이렇게 만들어진 두개의 배열을 각각 오름차순으로 정렬 한 후에 하나의 배열은 시작부터, 하나의 배열을 끝부터 시작한다. 

이미 이 배열에 구간의 합에 대한 경우의 수가 들어 있으니 이 두개의 배열의 합이 T를 만족하는 개수를 찾으면 된다.

다만 개수를 찾을 때 주의해야할게 있다. 구간합이 중복되는 경우가 반드시 있을 수 있다. 이때 일반적인 방법으로 갯수를 구하게 되면 올바른 값을 구할 수 없다. 그러므로 값을 볼때마다 해당 값이 중복되는 값인지 확인하는 과정이 필요하고 중복되는 경우 중복되는 A배열의 값 갯수 * B배열의 값 갯수를 곱해줘 카운팅 해줘야 한다.

이때 이걸 좀 편하게 하기 위해 나는 map을 이용했다. 또 자료형을 long형으로 하는걸 잊지말자.

/*
	21.01.12
	BOJ : 두 배열의 합 (https://www.acmicpc.net/problem/2143)
	투포인터
*/
#include <bits/stdc++.h>
using namespace std;

int A[1001];
int B[1001];
vector <long long int> subA;
vector <long long int> subB;
map <int, int> countingA;
map <int, int> countingB;

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

	int T, N,M;
	cin >> T;

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

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

	for (int i = 0; i < N; i++) {
		int sum = 0;
		for (int j = i; j < N; j++) {
			sum += A[j];
			subA.push_back(sum);
			countingA[sum]++;
		}
	}
	
	for (int i = 0; i < M; i++) {
		int sum = 0;
		for (int j = i; j < M; j++) {
			sum += B[j];
			subB.push_back(sum);
			countingB[sum]++;
		}
	}

	sort(subA.begin(), subA.end());
	sort(subB.begin(), subB.end());
	
	int p1 = 0;
	int p2 = subB.size() - 1;
	long long int cnt = 0;
	
	while (true) {
	int sum = subA[p1] + subB[p2];
		if (sum > T) {
			p2--;
		}
		else if (sum < T) {
			p1++;
		}
		else { // sum == T
			//A에서 갯수세기.
			long long int curNumA = subA[p1];
			long long int curNumB = subB[p2];
	
			long Acount = countingA[curNumA];
			long Bcount = countingB[curNumB];

			cnt = cnt + (Acount * Bcount);

			p1 += Acount;
			p2 -= Bcount;
		}
	
		if (p2 < 0 || p1 >= subA.size()) break;
	}
	
	cout << cnt;
	
	return 0;
}