[백준] 2143: 두 배열의 합

0. 문제 주소

 

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

2143번: 두 배열의 합

 

 

1. 풀이

 

먼저 A와 B 배열에 대해, 가능한 모든 부배열의 합을 구해 놓는다.

 

우리가 원하는 상황은, A의 부배열 합 + B의 부배열 합 = T가 되는 상황이다.

 

A의 부배열 합이 결정되면, 상황을 만족시켜야 할 B의 부배열 합은 바로 정해지는 것이다.

 

이것을 lower_bound와 upper_bound를 이용해 계산해준다.

 

lower_bound와 upper_bound는 각각 처음으로 (이상, 초과)인 원소의 포인터를 리턴해 주므로 

 

upper_bound - lower_bound를 이용하여, A의 부배열 합에 따라 만족하는 B의 부배열 합의 개수를 구해주면 된다.

 

2. 풀이 코드

 

* 유의할 점

 

 

#include <bits/stdc++.h>
#define MAX 1005
#define ll long long

using namespace std;

ll T;
int n, m;
ll A[MAX], B[MAX];
vector<ll> pA, pB;

int main(){
    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r", stdin);
    #endif // ONLINE_JUDGE

    scanf("%lld", &T);

    scanf("%d", &n);
    for (int i=1;i<=n;i++){
        scanf("%lld", &A[i]);
    }
    scanf("%d", &m);
    for (int i=1;i<=m;i++){
        scanf("%lld", &B[i]);
    }

    for (int i=1;i<=n;i++){
        for (int j=i;j<=n;j++){
            if (i == j) pA.push_back(A[i]);
            else{
                ll temp = 0LL;
                for (int x=i;x<=j;x++){
                    temp += A[x];
                }
                pA.push_back(temp);
            }
        }
    }

    for (int i=1;i<=m;i++){
        for (int j=i;j<=m;j++){
            if (i==j) pB.push_back(B[i]);
            else{
                ll temp = 0LL;
                for (int x=i;x<=j;x++){
                    temp += B[x];
                }
                pB.push_back(temp);
            }
        }
    }

    sort(pA.begin(), pA.end());
    sort(pB.begin(), pB.end());

    ll cnt = 0LL;

    for (int a=0;a<pA.size();a++){
        ll b = T - pA[a];
        cnt += upper_bound(pB.begin(), pB.end(), b) - lower_bound(pB.begin(), pB.end(), b);
    }
    printf("%lld\n", cnt);

    return 0;
}