[boj] 백준 2143 두 배열의 합 (c++) - 투포인터

[문제]

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

2143번: 두 배열의 합

 

[풀이]

a와 b 배열에 대해 각각의 부분합을 모두 구해 저장해준다.

이후 sort를 이용해 정렬한 뒤 합이 t가 되게 하는 경계를 찾아 경우의 수를 구해준다.

c++에서는 upper_bound, lower_bound 함수가 제공되어 쉽게 풀 수 있었다.

 

upper_bound : begin(), end() 범위 내에서 value 값을 초과하는 가장 작은 이터레이션을 반환한다.

lower_bound: begin(), end() 범위 내에서 value 값 이상이 나타나는 가장 작은 이터레이션을 반환한다.

 

[코드]

 

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <cstring>
#include <cmath>
#define INF 987654321

using namespace std;

int t, n, m;
int a[1001], b[1001];

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

    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];
    }

    vector<int> av, bv;

    //a배열의 모든 부분합
    int sum;
    for(int i=0; i<n; i++){
        sum = 0;
        for(int j=i; j<n; j++){
            sum += a[j];
            av.push_back(sum);
        }
    }

    //b배열의 모든 부분합
    for(int i=0; i<m; i++){
        sum = 0;
        for(int j=i; j<m; j++){
            sum += b[j];
            bv.push_back(sum);
        }
    }

    sort(av.begin(), av.end());
    sort(bv.begin(), bv.end());

    long long ans = 0;
    for(auto value : av){
        int temp = t - value;
        long long upper_index = upper_bound(bv.begin(), bv.end(), temp) - bv.begin();
        long long lower_index = lower_bound(bv.begin(), bv.end(), temp) - bv.begin();
        ans += upper_index - lower_index;
    }

    cout << ans;
}