[백준 2143] 두 배열의 합

 

 Map, 투 포인터, 이진 탐색 등 여러 방법으로 접근 가능한 문제. 브루트 포스로 해결하면 O(n^2 * m^2)의 시간 복잡도를 가지기 때문에 시간 내에 풀 수 없다.

 핵심 아이디어는 심플한데, 각각의 부 배열 합을 미리 생성해두는 것이다. 모든 부 배열 합을 알아내기 위해서는 O(n^2)이면 충분하므로, n과 m의 최댓값이 1,000인 위 문제에서는 모든 부 배열 합을 미리 구해둬도 상관없다.

 이를 어떻게 저장해둘지는 자유인데, 리스트든 맵이든 해시 테이블이든 본인이 사용할 로직에 맞춰 자료구조를 선택하면 된다. 각각의 자료구조와 로직은 일장일단이 있다.

 나는 해시 테이블(C++이기에, unordered_map을 사용)을 이용하고, 내장된 해시 탐색 로직을 그대로 활용하기로 했다. 배열B에 대해 모든 부 배열 합 별 갯수를 unordered_map에 담아둔다. 그리고 배열A에 대한 모든 부 배열 합을 탐색하면서 아까 생성해둔 unordered_map에 T-현재 탐색 중인 배열A의 부 배열 합 값이 있는지 찾아서, 있다면 그 value 값을 결과에 더한다. 이 때 결과 값은 500,000 * 500,000 까지 올라갈 수 있으므로 자료형에 유의해야 한다.(n과 m이 1,000이고 배열 A와 B의 모든 원소가 0일 때, t가 0인 경우)

 

#include <iostream>
#include <unordered_map>

using namespace std;

int a[1000];
int b[1000];

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

    int t, n, m;

    cin >> t >> n;

    for(int i=0; i<n; i++) {
        cin >> a[i];
    }

    cin >> m;

    for(int i=0; i<m; i++) {
        cin >> b[i];
    }

    unordered_map<int, int> bMap;

    for(int i=0; i<m; i++) {
        int sum = 0;
        for(int j=i; j<m; j++) {
            sum+=b[j];
            bMap[sum]++;
        }
    }

    long long result = 0;

    for(int i=0; i<n; i++) {
        int sum = 0;
        for(int j=i; j<n; j++) {
            sum+=a[j];

            auto bElement = bMap.find(t-sum);
            if(bElement!=bMap.end()) {
                result += (*bElement).second;
            }
        }
    }

    cout << result;
}