골드3 - 백준 2143 두 배열의 합

백준 2143 두 배열의 합

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

접근방법

부 배열의 합이 T가 되는 경우를 구하기 위해 각각의 배열의 모든 부 배열들의 합을 계산했고, 각 합한 값들이 몇번 나오는 지 수를 세어주었다. 그리고 T에서 A배열에서 나올 수 있는 부 배열의 합값을 빼서 얻은 수가 B배열에서 몇개 나올 수 있는 지 확인하여 서로 값들을 곱해서 경우의 수에 추가해주었다. 이렇게 모든 수들의 조합을 구할 수 있었다.

풀이

A, B배열 둘 다 combine 함수의 반복문을 통해서 모든 부 배열의 경우를 구해주었고 그 합값을 Hash Map의 Key로 사용해서 같은 합값의 개수를 저장해주었다.
그리고 mapA를 순회하면서 T에서 Key로 저장된 값을 뺀 나머지를 mapB에서 찾아서 각각의 개수를 곱해주었다. 차례차례 count변수에 더해주었고 mapA의 순회가 끝나면 count 값을 출력해주었다.

코드

#include <iostream>
#include <vector>
#include <unordered_map>

using namespace std;

vector<int> numbersA;
vector<int> numbersB;
unordered_map<int, long long> mapA;
unordered_map<int, long> mapB;

void combine()
{
	for (int i = 0; i < numbersA.size(); i++)
	{
		int sum = numbersA[i];
		long long t = mapA[sum];
		mapA[sum] = ++t;

		for (int j = i+1; j < numbersA.size(); j++)
		{
			sum += numbersA[j];
			long long temp = mapA[sum];
			mapA[sum] = ++temp;
		}
	}

	for (int i = 0; i < numbersB.size(); i++)
	{
		int sum = numbersB[i];
		long long t = mapB[sum];
		mapB[sum] = ++t;

		for (int j = i + 1; j < numbersB.size(); j++)
		{
			sum += numbersB[j];
			long long temp = mapB[sum];
			mapB[sum] = ++temp;
		}
	}
}

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

	int T;
	cin >> T;

	int N;
	cin >> N;
	for (int i = 0; i < N; i++)
	{
		int temp;
		cin >> temp;
		numbersA.push_back(temp);
	}

	int M;
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		int temp;
		cin >> temp;
		numbersB.push_back(temp);
	}

	combine();
	long long count = 0;

	for (auto cur : mapA)
	{
		int key = cur.first;
		long long num = cur.second;

		count += mapB[T - key] * num;
	}

	cout << count << endl;
}