[백준 2143번] 두 배열의 합 C++ 풀이

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

2143번: 두 배열의 합

 

문제 분석

배열 A와 B가 주어졌을 때, 각 배열의 부분 배열의 합을 더해 원하는 숫자가 되도록 하는 문제.

 

 

문제 풀이

처음에는 각각 A, B를 가리키는 투 포인터로 문제를 해결해보려고 했지만, 생각보다 이중 투 포인터를 하는 방식이 까다로워 다른 블로그를 참고해 이중탐색으로 풀었다.이중 탐색은 하나의 요소를 O(logN)만에 찾는 알고리즘으로, 주로 긴 배열 중 원하는 요소를 빠르게 찾고자 할 때 용이하다.

 

그렇다면 어떻게 배열의 부분 배열을 만들고 합을 찾는 과정에서 이중탐색을 적용할 수 있을까?

답은 부분 배열의 합을 계산한 뒤 배열로 따로 관리해주면 된다.

그러니까, A에서 나올 수 있는 부분 배열의 합(asum)과 B에서 나올 수 있는 부분배열의 합(bsum)을 구해,

asum의 요소 + bsum의 요소 = T 가 되는 경우의 수를 더해주면 된다.

 

이때 이중 탐색에서는 lower_bound와 upper_bound를 사용했다.

 

 

코드

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int t,i,j, n,m,a[1001],b[1001];
long long result;
int asum[999999],bsum[999999];
int as,bs,idx,bidx;
int main(){
    scanf("%d",&t);
    scanf("%d",&n);
    for(i=0;i<n;i++){
        scanf("%d",&a[i]);
    }
    scanf("%d",&m);
    for(i=0;i<m;i++){
        scanf("%d",&b[i]);
    }

    for(i=0;i<n;i++){
        as=0; 
        for(j=i;j<n;j++){
            as+=a[j];
            asum[idx++]=as;
        }
    }
    sort(asum,asum+idx);
    
    for(i=0;i<m;i++){
        bs=0;
        for(j=i;j<m;j++){
            bs+=b[j];
            bsum[bidx++]=bs;
        }
    }
    sort(bsum,bsum+bidx);
    
    for(i=0;i<idx;i++){
        int target=t-asum[i];
        result+=upper_bound(bsum,bsum+bidx,target)-lower_bound(bsum,bsum+bidx,target);
        
    }

    cout<<result<<endl;
    return 0;
}

 

 

마무리

참고로, result는 두개의 부분 배열이 모두 부분합이 T가 되는 경우를 만족하게 되면,

1,000 * 1,000 * 1,000 * 1,000으로 int 범위를 넘게 되어 long long을 사용해야 한다. 

(n, m이 모두 1000이고 각각의 요소가 0인 경우)