BOJ 2143 두 배열의 합

사용한 알고리즘

투포인터

알고리즘 설명

한 배열의 합에 모든 경우의 수를 모두 만들어 보고 배열에 넣는다.(총 nC2 = 최대 1000*999/2 = 약 50만)
두 배열로 100만개 나오는데, 이 두배열로 두 합이 T인 경우를 찾아본다.
두 배열을 각각 오름차순 정렬한다.
정렬 뒤에 이를 seqA 배열과 seqB 배열이라고 하면 seqA 배열 앞을 가리키는 포인터 하나, seqB 배열은 맨 뒤 요소를 가리키는 포인터 하나를 만든다.
각 포인터가 가리키는 seqA와 seqB의 합이 T보다 큰지 작은지 같은지를 판단한다.
두 합이 같은 경우에는 seqA와 seqB의 같은 값을 가지는 개수를 샌 뒤에 경우의 수를 추가시켜준다.
두 합이 T보다 작은 경우에는 seqA 포인터 값을 증가시켜 전체 합을 증가시켜준다.
두 합이 T보다 큰 경우에는 seqB 포인터 값을 감소시켜 전체 합을 감소시켜준다.
이를 반복하여 모든 seqA와 seqB를 훝어 T를 만들 수 있는 모든 경우의 수의 개수를 출력한다.

풀이

// baekjoon 2143 yechan
#include <cstdio>
#include <algorithm>
using namespace std;
const int MAX_N=1001;
const int MAX_NN= (MAX_N*(MAX_N+1))/2;
int T, N, M, A[MAX_N], B[MAX_N], tmp, sA, sB, pA, pB, cntA, cntB;
int seqA[MAX_NN], seqB[MAX_NN];

int main() {
	scanf("%d", &T);
	scanf("%d", &N);
	for (int i=1; i<=N; i++) {
		scanf("%d", &A[i]);
		A[i]+=A[i-1];
	}

// 배열의 가능한 연속적인 합의 개수를 모두 구함
	for (int i=1; i<=N; i++)
		for (int j=i; j<=N; j++, sA++)
			seqA[sA] = A[j]-A[i-1];

	scanf("%d", &M);
	for (int i=1; i<=M; i++) {
		scanf("%d", &B[i]);
		B[i]+=B[i-1];
	}

	for (int i=1; i<=M; i++)
		for (int j=i; j<=M; j++, sB++)
			seqB[sB] = B[j]-B[i-1];

// 이를 정렬한다.
	sort(seqA, seqA+sA);
	sort(seqB, seqB+sB);

// 두 포인터을 만들어 pA는 가장 앞쪽, pB는 가장 뒤쪽을 가리킨다.
	pA = 0;
	pB = sB-1;
	long long ret = 0;
	while (pA < sA && pB >= 0) {
		tmp = seqA[pA] + seqB[pB];
		if (tmp < T) pA++;
		else if (tmp > T) pB--;
// 두 포인터가 가지는 합이 같은 경우 경우의 수의 추가시켜준다.
		else {
			cntA=1, pA++;
			while (pA < sA && seqA[pA]==seqA[pA-1])
				pA++, cntA++;

			cntB=1, pB--;
			while (pB >= 0 && seqB[pB]==seqB[pB+1])
				pB--, cntB++;

			ret += 1LL*cntA*cntB;
		}
	}
	printf("%lld\n", ret);
	return 0;
}