문제 링크입니다: 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
지적, 조언, 질문 환영입니다! 댓글 남겨주세요~
'알고리즘 > BOJ' 카테고리의 다른 글
백준 2018번 수들의 합 5 (0) | 2019.01.29 |
---|---|
백준 14614번 Calculate! (0) | 2019.01.29 |
백준 2632번 피자 판매 (6) | 2019.01.27 |
백준 3020번 개똥벌레 (8) | 2019.01.27 |
백준 7453번 합이 0인 네 정수 (3) | 2019.01.27 |