BOJ 2143 : 두 배열의 합

• 문제 링크 : boj.kr/2143
• 난이도 : G3
• 태그 : 누적합, 이분탐색

2143번: 두 배열의 합

---

코드

#include <bits/stdc++.h>

#define all(x) (x).begin(), (x).end()

#define INF 0x7FFFFFFF

using namespace std;

using ll = long long;
using ld = long double;
using pii = pair<int,int>;
using pll = pair<ll, ll>;

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    ll T;
    cin >> T;
    int n;
    cin >> n;
    vector<ll> A(n+1);
    for(int i = 1; i <= n; i++) {
        cin >> A[i];
        A[i] += A[i-1];
    }
    int m;
    cin >> m;
    vector<ll> B(m+1);
    for(int i = 1; i <= m; i++) {
        cin >> B[i];
        B[i] += B[i-1];
    }
    vector<ll> arr1, arr2;
    for(int i = 0; i <= n; i++) {
        for(int j = i + 1; j <= n; j++) {
            arr1.emplace_back(A[j]-A[i]);
        }
    }
    for(int i = 0; i <= m; i++) {
        for(int j = i + 1; j <= m; j++) {
            arr2.emplace_back(B[j]-B[i]);
        }
    }
    sort(all(arr2));

    ll ans = 0;
    for(int i = 0; i < arr1.size(); i++) {
        ll target = T - arr1[i];
        ans += upper_bound(all(arr2), target) - lower_bound(all(arr2), target);
    }
    cout << ans;

    return 0;
}

---

풀이

누적합을 이용해 각각 O(N^2), O(M^2)으로 모든 부분배열의 합을 구해둔다.

A의 부분배열의 합을 순회하며 그 값에 해당하는 B의 부분배열의 합의 개수를 구한다.

이떄 N^2 * M^2으로 모든 경우를 확인하면 시간 초과가 나므로 B의 부분배열의 합의 개수를 이분탐색으로 구해준다.

이분탐색을 사용하므로 정렬해야 함에 유의해야 한다.