백준 2143 두 배열의 합 - 단순 브루트포스 c++

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

2143번: 두 배열의 합

 

배열별로 가질 수 있는 모든 부분합의 경우와 경우의 수를 우선 전부 구해 T가 되는 가지수를 구하면 되는 문제였다.

set를 활용해 key value 값으로 저장해 구현할수도 있지만 벡터를 활용해 해결하는 방법으로 풀어보았다.

 

lower bound upper bound에 대한 보다 자세한 설명은 이 분의 블로그 포스팅을 보면 될 것 같다.

https://blockdmask.tistory.com/168

[탐색] lower_bound, upper_bound

#include <iostream>
#include <vector>
#include <algorithm>
 
using namespace std;
long long T;
int n,m;
 
int main(void){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin>>T;
 
    cin>>n;
    vector<long long> A(n);
    for(int i=0; i<n; i++)
        cin>>A[i];
 
    cin>>m;
    vector<long long> B(m);
    for(int i=0; i<m; i++)
        cin>>B[i];
 
    vector<long long> Asums,Bsums;
    for(int i=0; i<n; i++){
        long long sum = A[i];
        Asums.push_back(sum);
        for(int j=i+1; j<n; j++){
            sum+=A[j];
            Asums.push_back(sum);
        }
    }
    for(int i=0; i<m; i++){
        long long sum = B[i];
        Bsums.push_back(sum);
        for(int j=i+1; j<m; j++){
            sum+=B[j];
            Bsums.push_back(sum);
        }
    }
 
    sort(Asums.begin(),Asums.end());
    sort(Bsums.begin(),Bsums.end());
    long long result=0;
    for(int i=0; i<Asums.size(); i++){
        int lowb=lower_bound(Bsums.begin(),Bsums.end(),T-Asums[i])-Bsums.begin();
        int highb=upper_bound(Bsums.begin(),Bsums.end(),T-Asums[i])-Bsums.begin();
        result += highb-lowb;
    }
    cout<<result;
 
 
}