[백준] 2143 : 두 배열의 합

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

2143번: 두 배열의 합

---

• N 에서 가능한 모든 부분합과 M 에서 가능한 모든 부분합은 둘 다 최대 1000 * 1000 개 이기 때문에, 완전 탐색은 불가능하다.
• 따라서 둘 중 더 큰 배열을 정렬해준 뒤, 나머지 배열에서 순차적으로 돌며 이진 탐색을 해 nlogn 으로 풀 수 있다.
• 이 때 하나의 부분합에서 부 배열 쌍이 성립하는 값이 여러개가 존재할 수 있기 때문에 모든 값을 탐색해줘야 하는데, c++ 에서는 algorithm 에서 제공해주는 벡터의 upper/lower bound 를 사용하면 편리하다.
• 좀 더 빠르게 풀기 위해서는 두 배열을 모두 정렬해준 뒤, 각각 앞쪽과 뒤쪽부터 시작하여(투 포인터 개념) T 값에 맞춰 움직이는데, 이러면 N + M 번 탐색으로 풀 수 있다.

---

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int T, n, m;
unsigned long long answer;
int arrN[1001];
int arrM[1001];

int main(void)
{
    cin >> T;
    
    cin >> n;
    vector<int> N;
    for(int i = 1 ; i <= n ; i++)
    {
        cin >> arrN[i];
        arrN[i] += arrN[i-1];                   // n 개의 수들에 대해 누적합을 구하고
        for(int j = 0 ; j < i ; j++)
        {
            N.push_back(arrN[i] - arrN[j]);     // 가능한 모든 부분합들에 대해서 저장함
        }
    }
    cin >> m;
    vector<int> M;
    for(int i = 1 ; i <= m ; i++)               // m 개 배열에 대해서도 마찬가지로 저장
    {
        cin >> arrM[i];
        arrM[i] += arrM[i-1];
        for(int j = 0 ; j < i ; j++)
        {
            M.push_back(arrM[i] - arrM[j]);
        }
    }

    sort(M.begin(), M.end());                   // 두 배열 중 한개 배열에 대해서 정렬을 해준 뒤

    for(int i = 0 ; i < N.size() ; i++)         // 나머지 배열의 원소들을 선형 탐색하면서 정렬된 배열에서 이진 탐색으로 맞는 값 확인
    {
        int target = T - N[i];                  // stl 에서 제공되는 알고리즘을 사용하면 편함...
        answer += (upper_bound(M.begin(), M.end(), target) - lower_bound(M.begin(), M.end(), target));
    }

    cout << answer << endl;
}