[C++] 백준 2143 - 두 배열의 합

<문제 링크>

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

11053번: 가장 긴 증가하는 부분 수열

<알고리즘 분류>

   - 누적 합(Cumulative Sum)

   - 이분 탐색(Binary Search)

 

<풀이> 

 우선 두 배열의 크기가 모두 1000이기 때문에, O(N^2)의 이중for문을 통해 가능한 모든 부분배열의 합의 경우의 수를  Asumcase, Bsumcase에 저장하였다. 

그 이후, O(logN)의 lower_bound, upper_bound를 활용하여 합을 만족하는 원소의 개수를 구하였다. 

 

마지막에 채점을 하는데 68%에서 틀렸다고 나왔는데, 알고 보니 답이 int형 범위를 초과하는 경우를 고려하지 못했다. 

ans도 long long 형으로 바꿔줘야, 정답이 된다.

<코드>

#include <iostream>
#include <vector> 
#include <algorithm>
using namespace std;

int n, m;
long long T;
int Asum[1001];
int Bsum[1001];
vector <long long> Asumcase;
vector <long long> Bsumcase;

int main(){
    long long ans = 0;
    cin >> T;
    cin >> n;
    for (int i=1; i<=n; i++){
        cin >> Asum[i];
        Asum[i] += Asum[i-1];
    }
    cin >> m;
    for (int i=1; i<=m; i++){
        cin >> Bsum[i];
        Bsum[i] += Bsum[i-1];
    }

    for (int i=1; i<=n; i++){
        for(int j=i; j<=n; j++){
            Asumcase.push_back(Asum[j]-Asum[i-1]);
        }
    }

    for (int i=1; i<=m; i++){
        for(int j=i; j<=m; j++){
            Bsumcase.push_back(Bsum[j]-Bsum[i-1]);
        }
    }

    sort(Asumcase.begin(), Asumcase.end());
    sort(Bsumcase.begin(), Bsumcase.end());

    for (int i=0; i<Asumcase.size(); i++){
        int low = lower_bound(Bsumcase.begin(), Bsumcase.end(), T-Asumcase[i]) - Bsumcase.begin();
        int high = upper_bound(Bsumcase.begin(), Bsumcase.end(), T-Asumcase[i])- Bsumcase.begin();

        ans += high - low;
    }

    cout << ans << "\n" ;

}