[백준]두 배열의 합(2143)

문제 링크 : [백준] 두 배열의 합(2143)

문제 설명

두 배열 A, B가 주어졌을 때, 두 배열의 각 부분 배열의 합이 T가 되는 경우의 수를 구하여라.
※ 부분 배열 : A[i], A[i+1],...A[j] (1 <= i <= j <= N(N은 배열 A의 사이즈))

입력

T(합의 되길 원하는 수, -1,000,000,000 <= T <= 1,000,000,000)
N_a(배열 A의 사이즈, 1<= N_a <=1,000)
A₁, A₂,A₃.... (배열 A의 원소, -1,000,000 <= A_i <= 1,000,000)
N_b(배열 B의 사이즈, 1 <= N_b <= 1,000)
B₁, B₂,B₃.... (배열 B의 원소, -1,000,000 <= B_i <= 1,000,000)

5
4
1 3 1 2
3
1 3 2

출력

7    <- 경우의 수

카테고리

#이진탐색

시간 복잡도 상한

O(N³) 의 경우, 1,000,000,000이므로, 시간제한 2초를 벗어납니다.
최대 O(N²*logN),약 10,000,000 에 해결해야 합니다.

해결 방법

1. 각 배열에서 나올 수 있는 모든 경우의 수를 각각 만듭니다.(2*N²)
2. 한쪽 배열(B)을 정렬합니다.(NlogN)
3. 정렬되지 않은 배열(A)를 순차적으로 방문하면서, 각 요소별로 정렬된 배열(B)에서 찾고자 하는 값을 이분 탐색으로 탐색합니다.(NlogN) 예시 : T가 5이고, A[i]가 3인 경우, B에서 2를 찾음
4. 단 B[i]에서 동일한 값이 많을 수 있으니, upper_bound(k)-lower_bound(k)의 값을 구합니다.(2*NlogN)
5. 위에서 구한 값들을 모두 더하여 답을 구합니다.

코드

#include<cstdio>
#include<vector>
#include<algorithm>
using namespace std;
int t,n,m,d[1000],e[1000],i,j;
long long s;
vector<int>v,w;
int main(){
    scanf("%d%d",&t,&n);
    for(i=0;i<n;i++)scanf("%d",d+i);
    scanf("%d",&m);
    for(i=0;i<m;i++)scanf("%d",e+i);
    for(i=0;i<n;i++)for(s=0,j=i;j<n;j++)v.push_back(s+=d[j]);
    for(i=0;i<m;i++)for(s=0,j=i;j<m;j++)w.push_back(s+=e[j]);
    sort(v.begin(),v.end());
    sort(w.begin(),w.end());
    for(s=i=0;i<v.size();i++)s+=(upper_bound(w.begin(),w.end(),t-v[i])-w.begin())-(lower_bound(w.begin(),w.end(),t-v[i])-w.begin());
    printf("%lld",s);
}