[백준 C++] 2143번 두 배열의 합

2143번: 두 배열의 합

문제 요약

문제

한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오.

예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다.

T(=5) = A[1] + B[1] + B[2]
      = A[1] + A[2] + B[1]
      = A[2] + B[3]
      = A[2] + A[3] + B[1]
      = A[3] + B[1] + B[2]
      = A[3] + A[4] + B[3]
      = A[4] + B[2] 

사용 알고리즘

누적합, 해시

입출력

• 입력: 첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1 ≤ m ≤ 1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다.
• 출력: 첫째 줄에 답을 출력한다. 가능한 경우가 한 가지도 없을 경우에는 0을 출력한다. ``` 예제1

입력 5 4 1 3 1 2 3 1 3 2 출력 7

## 풀이
일단 누적합을 이용해서 a와 b의 모든 부배열의 합을 구한다. 이후 그것을 a는 해시에 저장하고 b는 백터에 저장한 후 b를 하나씩 불러와서 T에서 뺀 후 그것이 a의 부배열의 합에 존재하는지 확인한다. 해시를 사용하여 빠르게 접근하고 부배열의 합이 여러개 존재하면 여러개를 더한다.

## 어려웠던 점
map을 잘 안써서 배열로 했다가 배열이 너무 커서 실패했다. 

## 배운 점 / 느낀 점
일단 애매하면 long long을 박고 시작하자. 해시를 사용하는 법을 기억하자.

## 전체 코드
```cpp
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
using namespace std;

long long n, m, t;
vector<long long> a;
map<long long,long long> asum;
vector<long long> b;
vector<long long> bsum;

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

    cin >> t;

    cin >> n;
    a = vector<long long>(n+1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        if(i != 0){
            a[i] += a[i-1];
        }
    }
    cin >> m;
    b = vector<long long>(m+1, 0);
    for (int i = 1; i <= m; i++) {
        cin >> b[i];
        if(i != 0){
            b[i] += b[i-1];
        }
    }
    for (int i = 0; i < n; i++) {
        for (int j = i+1; j <= n; j++) {
            asum[a[j]-a[i]] += 1;
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = i+1; j <= m; j++) {
            bsum.push_back(b[j]-b[i]);
        }
    }
    long long c = 0;
    for(long long i : bsum){
        c += asum[t-i];
    }
    cout << c;
    return 0;
}