[백준 BOJ] 2143번 - 두 배열의 합 (C++)

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

2143번: 두 배열의 합

가장 먼저 든 생각은 연속된 수의 합과 이에 대한 경우의 수를 구할 수 있는 배열을 만들어보자였는데, 메모리 제한이 작기 때문에 map 자료구조를 이용하기로 했다. 연속된 수의 합을 구할 때는 그냥 이중 for문으로 쉽게 구현할 수 있다.

주의해야 할 점은 답으로 제출하는 경우의 수가 int 형 범위를 넘어갈 수 있으므로 long 형 타입을 써줘야한다.

#include <iostream>
#include <cmath>
#include <cstring>
#include <algorithm>
#include <memory.h>
#include <map>

#define endl '\n'
#define ll long long
#define pii pair<int, int>
#define max 987654321

using namespace std;

int T, n, m;
int A[1000];
int B[1000];
map<int, ll> s;

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    ll result = 0;
    cin >> T >> n;
    for (int i = 0; i < n; i++)
    {
        cin >> A[i];
    }
    int sum = 0;
    for (int i = 0; i < n; i++)
    {
        sum = A[i];
        s[sum]++;
        for (int j = i + 1; j < n; j++)
        {
            sum += A[j];
            s[sum]++;
        }
    }
    cin >> m;
    for (int i = 0; i < m; i++)
    {
        cin >> B[i];
    }
    for (int i = 0; i < m; i++)
    {
        sum = B[i];
        result += s[T - sum];
        for (int j = i + 1; j < m; j++)
        {
            sum += B[j];
            result += s[T - sum];
        }
    }
    cout << result << endl;
    return 0;
}