[BOJ] 백준 2143 두 배열의 합

문제 링크

www.acmicpc.net/problem/2143

2143번: 두 배열의 합

 

풀이

백준 7453 - 합이 0인 네 정수 문제와 유사합니다.

위 문제에선 $a, b$의 모든조합, $c, d$의 모든 조합을 나눠 생각했고, 이 문제에서는 $a$의 모든 부분 배열의 합, $b$의 모든 부분 배열의 합을 구하여 같은 방식으로 답을 구하면 됩니다.

 

$[T - (a$의 부분 배열$_i$ 의 합)$]$이 $(b$의 모든 부분 배열의 합$)$을 저장해놓은 배열에 있는지 확인합시다.

 

정답 코드

#include <bits/stdc++.h>

#define INF 0x3f3f3f3f
#define ft first
#define sd second
#define all(x) (x).begin(), (x).end()
using namespace std;
using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;
using vi = vector<int>;
using vb = vector<bool>;
using vs = vector<string>;
using vd = vector<double>;
using vll = vector<ll>;
using vpii = vector<pii>;
using vvi = vector<vi>;
using vvb = vector<vb>;
using vvll = vector<vll>;
using vvpii = vector<vpii>;

int a[1111], b[1111];
int t, n, m;
vi p;

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> t >> n;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        sum += a[i];
        for (int j = 0, val = sum; j < i + 1; j++) {
            p.push_back(val);
            val -= a[j];
        }
    }
    sort(all(p));
    cin >> m;
    sum = 0;
    ll ans = 0;
    for (int i = 0; i < m; i++) {
        cin >> b[i];
        sum += b[i];
        for (int j = 0, val = sum; j < i + 1; j++) {
            ans += upper_bound(all(p), t - val) - lower_bound(all(p), t - val);
            val -= b[j];
        }
    }
    cout << ans;
}