2143번

2143번 - 두 배열의 합

완전 탐색에서 투 포인터를 이용해서 문제를 푸는 방식.

각각의 배열의 부분합을, 각각의 sum1, sum2 에 저장한 후에, 

이분탐색(upper_bound, lower_bound) 를 이용해서 문제를 풀 수 있었다.

<정답 코드>

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
vector<int> sum1;
vector<int> sum2;
void makeAll(vector<int> X,int k,int goal)
{
    int left = 0, right = 0;
    int sum = 0;
 
    while (left<X.size())
    {
        sum += X[right++];
        
        if (k == 1)
        {
            sum1.push_back(sum);
        }
        else
        {
            sum2.push_back(sum);
        }
 
        if (right == X.size())
        {
            left++;
            right = left;
            sum = 0;
        }
    }
}
int main()
{
    //freopen("input.txt", "r", stdin);
    int t, n, m;
    long long ans = 0;
    scanf("%d%d", &t, &n);
    vector<int> A(n);
 
    for (int i = 0; i < n; i++)
    {
        scanf("%d", &A[i]);
    }
    scanf("%d", &m);
    vector<int> B(m);
    for (int i = 0; i < m; i++)
    {
        scanf("%d", &B[i]);
    }
 
    makeAll(A,1,t);
    makeAll(B,2,t);
    sort(sum1.begin(), sum1.end());
    sort(sum2.begin(), sum2.end());
 
    int i = 0;
 
    while (i < sum1.size())
    {
        auto u = upper_bound(sum2.begin(), sum2.end(), t - sum1[i]);
        auto l = lower_bound(sum2.begin(), sum2.end(), t - sum1[i]);
 
        ans += u - l;
        i++;
    }
 
 
    printf("%lld\n", ans);
    return 0;
}