[BOJ] 두 배열의 합 2143 C++ 풀이

문제

두 배열의 합

접근방법

각 배열 a,b의 부분 합을 저장하는 배열 sA, sB를 각각 선언해준 다음 각각 오름차순으로 정렬 해주고 나서 이진탐색을 활용하여 T - sA[i]를 만족하는 수가 sB에 몇개 존재하는 지를 총합해서 구하는 방식으로 해결하였다.

배열 a의 부분 합을 저장하는 배열 sA = {a[0], a[0]+a[1], a[0]+a[1]+a[2], …, a[0]+ … a[n]} 를 선언해 주고 마찬가지로 배열 b의 부분 합의 배열 sB도 선언해 주었다.

아래의 반복문을 통해 T를 만족하는 a,b의 부분 합을 구할 수 있다.

for(int i=0; i<sA.size(); i++)
{
    left = lower_bound(sB.begin(), sB.end(), t - sA[i]) - sB.begin();
    right = upper_bound(sB.begin(), sB.end(), t - sA[i]) - sB.begin();
    cnt += right - left;
}

구현

#include<iostream>
#include<vector>
#include<algorithm>
typedef long long ll;
using namespace std;

int main(void)
{
    ios::sync_with_stdio(false); cin.tie(0);
    int t, n, m, num, left, right;
    ll sum = 0;
    ll cnt = 0;
    vector<int> a, b;
    vector<ll> sA, sB;
    cin>>t;
    cin>>n;
    for(int i=0; i<n; i++)
    {
        cin>>num;
        a.push_back(num);
    }

    cin>>m;
    for(int i=0; i<m; i++)
    {
        cin>>num;
        b.push_back(num);
    }

    for(int i=0; i<n; i++)
    {
        sum = a[i];
        sA.push_back(sum);
        for(int j=i+1; j<n; j++)
        {
            sum += a[j];
            sA.push_back(sum);
        }
    }

    for(int i=0; i<m; i++)
    {
        sum = b[i];
        sB.push_back(sum);
        for(int j=i+1; j<m; j++)
        {
            sum += b[j];
            sB.push_back(sum);
        }
    }

    sort(sA.begin(), sA.end());
    sort(sB.begin(), sB.end());

    for(int i=0; i<sA.size(); i++)
    {
        left = lower_bound(sB.begin(), sB.end(), t - sA[i]) - sB.begin();
        right = upper_bound(sB.begin(), sB.end(), t - sA[i]) - sB.begin();
        cnt += right - left;
    }

    cout<<cnt<<'\n';
    return 0;
}