두 배열의 합 2143

문제

접근 방법

누적 합 + 이분 탐색 문제이다.
나올 수 있는 모든 범위의 합을 구하고 그것을 이용해 T에서 A 부 배열의 합을 뺀 값이 B 부 배열의 합에 나오는지 확인하는 것이다.

T=A+B이기에 T-A=B라는 것이다.

누적 합은 범위의 합을 구할 수 있다.
해당 방법을 사용하여 모든 부 배열의 합을 구하면 된다.

코드

#include <iostream>
#include <vector>
#include <algorithm>
typedef long long ll;
using namespace std;
void vInput(vector<ll> &v, int &size)
{
    v.push_back(0);
    for (int i = 1, j; i <= size; ++i)
    {
        cin >> j;
        v.push_back(j);
        v[i] += v[i - 1];
    }
}
void getSum(vector<ll> &v, vector<ll> &vSum)
{
    for (int i = 0; i < v.size(); ++i)
        for (int j = i + 1; j < v.size(); ++j)
            vSum.push_back(v[j] - v[i]);
    sort(vSum.begin(), vSum.end());
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0);
    int n, m;
    ll T, ret = 0;
    vector<ll> A, B, sumA, sumB;
    cin >> T >> n;
    vInput(A, n);
    cin >> m;
    vInput(B, m);
    getSum(A, sumA);
    getSum(B, sumB);
    for (ll i : sumA)
    {
        ll targetNum = T - i;
        int first = lower_bound(sumB.begin(), sumB.end(), targetNum) - sumB.begin();
        int last = upper_bound(sumB.begin(), sumB.end(), targetNum) - sumB.begin();
        ret += last - first;
    }
    cout << ret;
    return 0;
}

풀이

실수로 binary_search로 값이 존재하는 지만 확인하고 ret를 1 증가시켰다.
부 배열의 합이 동일한 값이 여러 개 있을 수 있는데 그것을 까먹고 작성한 것이다.
또한 인덱스를 구하려면 begin을 빼야 하는 데 까먹고 잘못된 방법으로 접근했다.

map 자료형을 활용하는 방안으로도 풀 수 있는 것 같다.