(C++) - 백준(BOJ) 2143번 : 두 배열의 합

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

2143번: 두 배열의 합

이분탐색으로 푼 문제였습니다.

 

풀이방법

 1. vector a, b에 입력을 받습니다.

 

 2. i ~ j까지의 누적합을 a, b 각각에 저장합니다.

 

 3. 이분탐색을 위해 b를 정렬합니다.

 

 4. a + b = t이므로 모든 a에 대해 b가 t - a인 값을 찾습니다. 해당 값이 여러개 있을 수 있으므로 lower_bound와 upper_bound의 index를 구해 둘의 차이를 ans에 더해줍니다.

 

Code

#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll n, m, t, ans;
int main(){
    cin >> t >> n;
    vector <ll> a(n);
    for(int i = 0; i < n; i++) cin >> a[i];
    cin >> m;
    vector <ll> b(m);
    for(int i = 0; i < m; i++) cin >> b[i];
    for(int i = 0; i < n; i++){
        ll sum = a[i];
        for(int j = i+1; j < n; j++){
            sum += a[j];
            a.push_back(sum);
        }
    }

    for(int i = 0; i < m; i++){
        ll sum = b[i];
        for(int j = i+1; j < m; j++){
            sum += b[j];
            b.push_back(sum);
        }
    }
    sort(b.begin(),b.end());
    for(int i = 0; i < a.size(); i++){
        int idx = lower_bound(b.begin(),b.end(),t - a[i]) - b.begin();
        int endIdx = upper_bound(b.begin(),b.end(),t - a[i]) - b.begin();
        ans += endIdx - idx;
    }
    cout << ans << '\n';
}