백준 2143번 두 배열의 합

문제 링크입니다: https://www.acmicpc.net/problem/2143

N, M이 최대 1000이기 때문에 미리 시간복잡도 O(N^2)으로 모든 부분합을 전처리해주고 lower_bound, upper_bound를 이용하면 쉽게 풀 수 있는 문제였습니다.

*답의 범위는 int 범위를 초과하므로 result는 long long이여야합니다.

#include <iostream>

#include <vector>

#include <algorithm>

using namespace std;

 

int main(void)

{

        ios_base::sync_with_stdio(0);

        cin.tie(0);

        long long T;

        cin >> T;

 

        int N;

        cin >> N;

        vector<long long> A(N);

        for (int i = 0; i < N; i++)

                 cin >> A[i];

 

        int M;

        cin >> M;

        vector<long long> B(M);

        for (int i = 0; i < M; i++)

                 cin >> B[i];

 

        vector<long long> v, v2;

        //전처리

        for (int i = 0; i < N; i++)

        {

                 long long sum = A[i];

                 v.push_back(sum);

                 for (int j = i + 1; j < N; j++)

                 {

                         sum += A[j];

                         v.push_back(sum);

                 }

        }

 

        for (int i = 0; i < M; i++)

        {

                 long long sum = B[i];

                 v2.push_back(sum);

                 for (int j = i + 1; j < M; j++)

                 {

                         sum += B[j];

                         v2.push_back(sum);

                 }

        }

 

        sort(v.begin(), v.end());

        sort(v2.begin(), v2.end());

        long long result = 0;

        for (int i = 0; i < v.size(); i++)

        {

                 int low = lower_bound(v2.begin(), v2.end(), T - v[i]) - v2.begin();

                 int high = upper_bound(v2.begin(), v2.end(), T - v[i]) - v2.begin();

 

                 result += high - low;

        }

        cout << result << "\n";

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~