C++ / 백준 / 2143 / 두 배열의 합

문제

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

2143번: 두 배열의 합

문제풀이

부분 집합 중 연속된 부분으로 조합을 짜야한다.

먼저 A집합에 대해 이중 for문으로 메모이제이션을 이용해 연속된 부분의 합들을 구하고 sumA[합]의 개수를 늘려준다.

그 다음 B집합에 대해 똑같이 구한다.

대신에 sum을 구하면 sumA[T-sum]의 값을 answer에 더해준다.

 

코드

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

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

	int T(0);
	cin >> T;
	int N(0);
	int sum(0);
	int idx1(0), idx2(0);
	long long answer(0);
	cin >> N;
	unordered_map<int, int>sumA;
	vector<int>A(N, 0);
	for (idx1 = 0; idx1 < N; ++idx1)
		cin >> A[idx1];

	for (idx1 = 0; idx1 < N; ++idx1) {
		sum = 0;
		for (idx2 = idx1; idx2 < N; ++idx2) {
			sum += A[idx2];
			sumA[sum]++;
		}
	}

	cin >> N;
	vector<int>B(N, 0);

	for (idx1 = 0; idx1 < N; ++idx1)
		cin >> B[idx1];

	for (idx1 = 0; idx1 < N; ++idx1) {
		sum = 0;
		for (idx2 = idx1; idx2 < N; ++idx2) {
			sum += B[idx2];
			answer += sumA[T - sum];
		}
	}

	cout << answer;
}