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

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

2143번: 두 배열의 합

 

코드

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
int main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    
    long long t;
    int n,m;
    cin>>t;
    cin>>n;
    int a[n];
    for(int i=0;i<n;i++)
    {
        cin>>a[i];
    }
    cin>>m;
    int b[m];
    for(int i=0;i<m;i++)
    {
        cin>>b[i];
    }
    vector<int> paa;
    vector<int> pab;
    for(int i=0;i<n;i++)
    {
        paa.push_back(a[i]);
        int sum=a[i];
        for(int j=i+1;j<n;j++)
        {
            sum=sum+a[j];
            paa.push_back(sum);
        }
    }
    for(int i=0;i<m;i++)
    {
        pab.push_back(b[i]);
        int sum=b[i];
        for(int j=i+1;j<m;j++)
        {
            sum=sum+b[j];
            pab.push_back(sum);
        }
    }
    
    sort(paa.begin(),paa.end());
    sort(pab.begin(),pab.end());
    long long res=0;
    for(int i=0;i<paa.size();i++)
    {
        res+=upper_bound(pab.begin(),pab.end(),t-paa[i])-lower_bound(pab.begin(),pab.end(),t-paa[i]);
    }
    cout<<res;
    return 0;
}

 

풀이

 각 a, b 배열의 모든 가능한 부 배열의 합을 27~36행, 37~46행을 통해서 paa, pab벡터에 넣어준다. 그 후에 각 벡터를 오름차순으로 정렬한 뒤 upper_bound와 lower_bound 함수를 사용하여 합이 t가 되는 부 배열 쌍의 개수를 구해준다. upper_bound와 lower_bound의 차를 이용해서 원소의 개수를 구하는 방법은 매우 유용한 거 같으니 꼭 사용할 줄 알아야 할 것 같다!

upper_bound와 lower_bound 함수의 사용법은 아래의 링크에서 확인할 수 있다.

 

https://zz12345.tistory.com/17

백준 10816번 : 숫자 카드 2 (C++) (upper_bound , lower_bound)