백준 2143번 - 두 배열의 합

백준 2143번 - 두 배열의 합

https://www.acmicpc.net/problem/2143

문제

• 배열 A와 B가 있다.

• 부배열은 배열의 부분 배열이다.

• A = {1, 3, 1, 2}, B = {1, 3, 2} 인경우, A와 B의 부배열 합이 T인 경우의 수를 모두 찾아라.

입력

• 첫째 줄 : T(-1,000,000,000 ≤ T ≤ 1,000,000,000) 

• 다음 줄 : n(1 ≤ n ≤ 1,000) 

• A[1] 부터 A[n]까지 입력

• 다음 줄 : m(1 ≤ n ≤ 1,000)

• B[1] 부터 B[n]까지 입력

출력

• 경우의 수를 출력

• 없을 경우 0을 출력

접근

• A로 만들 수 있는 부배열의 합을 미리 다 구한다.

• B로 만들 수 있는 부배열의 합을 미리 다 구한다.

• B를 정렬 (바이너리 서치를 위함)

• A의 원소를 하나씩 탐색하며 T와의 차이 값이 B에 몇 개 존재하는 지를 찾는다.

C++ Code

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
​
const int INF = 2e8;
int t;
int n, m;
int a[1000], b[1000];
vector<int> v, w;
​
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> t;
    
    cin >> n;
    for (int i = 0; i < n; i++) cin >> a[i];
​
    cin >> m;
    for (int i = 0; i < m; i++) cin >> b[i];
​
    //a로 만들 수 있는 부분합
    for (int i = 0; i < n; i++) {
        int sum = a[i];
        v.push_back(sum);
        for (int j = i + 1; j < n; j++) {
            sum += a[j];
            v.push_back(sum);
        }
    }
​
    //b로 만들 수 있는 부분합
    for (int i = 0; i < m; i++) {
        int sum = b[i];
        w.push_back(sum);
        for (int j = i + 1; j < m; j++) {
            sum += b[j];
            w.push_back(sum);
        }
    }
    
    sort(w.begin(), w.end());
​
    long long ans = 0;
    for (auto item : v)
    {
        int diff = t - item;
        auto ub = upper_bound(w.begin(), w.end(), diff);
        auto lb = lower_bound(w.begin(), w.end(), diff);
        ans += (ub - lb);
    }
    cout << ans;
​
    return 0;
}