[BOJ] 두 배열의 합

문제

한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오.

예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다.

T(=5) = A[1] + B[1] + B[2] = A[1] + A[2] + B[1] = A[2] + B[3] = A[2] + A[3] + B[1] = A[3] + B[1] + B[2] = A[3] + A[4] + B[3] = A[4] + B[2]

입력

첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다.

출력

첫째 줄에 답을 출력한다. 가능한 경우가 한 가지도 없을 경우에는 0을 출력한다.

 

2143

맞았습니다!!

14408

136

C++14 / 수정

1552

21시간 전

 

1) 비슷한 문제 

https://www.acmicpc.net/status?from_mine=1&problem_id=2143&user_id=20shinee

채점 현황

 

풀이 

2020/02/10 - [BOJ/C++] - [BOJ] 합이 0인 네 정수

[BOJ] 합이 0인 네 정수

 

2) 완전 탐색. 

배열 A와 B를 모두 사용해서 T가 나와야 한다. 

 

3) A배열의 모든 조합과 B배열의 모든 조합을 만들었다. 

그 다음엔 탐색 시간을 줄이기 위해 (모든 조합이니까 굉장히 많은 값들을 탐색해야하니까) 이분탐색을 한다. 

 

4) 이분 탐색을 위해 일단 B배열의 조합을 오름차순으로 정렬하고, 

target = T - A배열의 조합

upper_bound(B배열의 조합 중 target 보다 큰 값의 위치)

lower_bound(B배열의 조합 중 target이상인 값의 위치)

 

합해서 T가 되는 값의 쌍의 개수는 upper - lower의 개수의 합이다. 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
 
typedef long long ll;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    ll t;
    int n, m;
    cin >> t >> n;
 
    vector<int> a, b;
 
    for (int i = 0; i < n; i++) {
        int tmp;
        cin >> tmp;
        a.push_back(tmp);
    }
 
    cin >> m;
 
    for (int i = 0; i < m; i++) {
        int tmp;
        cin >> tmp;
        b.push_back(tmp);
    }
 
    vector<ll> resA, resB;
 
    //모든 부분합을 구한다.
    for (int i = 0; i < n; i++) {
        ll tmp = a[i];
        resA.push_back(tmp);
        for (int j = i+1; j < n; j++) {
            tmp += a[j];
            resA.push_back(tmp);
        }
    }
 
    
    for (int i = 0; i < m; i++) {
        ll tmp = b[i];
        resB.push_back(tmp);
        for (int j = i+1; j < m; j++) {
            tmp += b[j];
            resB.push_back(tmp);
        }
    }
 
    sort(resB.begin(), resB.end());
    // cout << "debug A ";
    // for (int i = 0; i < resA.size(); i++) cout << resA[i] << ' ';
    // cout << '\n';
    // cout << "debug B ";
    // for (int i = 0; i < resB.size(); i++) cout << resB[i] << ' ';
 
    ll ans = 0;
    for (int i = 0; i < resA.size(); i++) {
        ll diff = t - resA[i]; //이 차이만큼을 B가 채우면 ok 
 
        vector<ll> ::iterator up = upper_bound(resB.begin(), resB.end(), diff);
        vector<ll> ::iterator lo = lower_bound(resB.begin(), resB.end(), diff);
        ans += up-lo;     
    }
    cout << ans << '\n';
 
    return 0;
}