백준 - 2143 두 배열의합

 

해결과정 - 해시맵, 누적합

문제를 보았을때 각각의 수가 나오는 경우의 수를 배열로 저장하면 되겠다고 생각하였지만 100억만큼의 배열이 요구되었으므로 해쉬가 필요하다고 생각하였다. 직접 구현하는 것도 좋지만 unordered_map을 사용하면 간단하게 구현할 수 있다.

그리고 순차적인 합이 부 배열이라는 문구를 본뒤 본능적으로 누적합으로 캐싱이 필요한 문제인지 생각해보았는데 역시 필요하여 누적합과 unordered_map을 통해 문제를 해결할 수 있었다.

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <string>
#include <unordered_map>
#define FAST ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)

typedef long long ll;

using namespace std;

ll T;
ll n, m;
vector<int> a, b;
unordered_map<ll, ll> a_dp;
unordered_map<ll, ll> b_dp;
int main() {
    FAST;

    cin >> T >> n;
	a.resize(n + 1);

    for (int i = 1; i <= n; i++) {
		ll x;
		cin >> x;
		a[i] = a[i - 1] + x;
	}

	cin >> m;
	b.resize(m + 1);

	for (int i = 1; i <= m; i++) {
		ll x;
		cin >> x;
		b[i] = b[i - 1] + x;
	}

	// i ~ j 까지는 a[j] - a[i - 1]
	for (int i = 0; i < n ; i++) {
		for (int j = 1; j <= n - i; j++) {
			ll value = a[j + i] - a[j - 1];
			a_dp[value]++;
		}
	}

	for (int i = 0; i < m; i++) {
		for (int j = 1; j <= m - i; j++) {
			ll value = b[j + i] - b[j - 1];
			b_dp[value]++;
		}
	}

	ll result = 0;
	for (auto it : a_dp) {
		ll cacl = T - it.first;
		if (b_dp[cacl] > 0) {
			result += it.second * b_dp[cacl];
		}
	}

	cout << result << "\n";
    return 0;
}