크기가 $N,M$인 두 배열이 주어진다.
두 배열에서 각각 부분배열 하나씩을 뽑은 합이 $T$가 될 경우의 수를 구하는 문제다.
$N$이 1000이라 $O(N^2)$으로는 불가능하다. 처음에는 map을 이용해서 풀려고했는데 메모리 크기도 작다보니 메모리초과가 발생해서 풀 수 없다.
lower_bound, upper_bound를 이용한 $O(N^2 logN)$ 풀이와
two pointer를 이용한 $O(N^2+M^2)$풀이가 존재한다.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int T;
int N, M;
int A[1001], B[1001];
vector<int> vb;
int main() {
scanf("%d", &T);
scanf("%d", &N);
for (int n = 0;n < N;n++) scanf("%d", &A[n]);
scanf("%d", &M);
for (int n = 0;n < M;n++) scanf("%d", &B[n]);
for (int n = 0;n < M;n++) {
int sum = 0;
for (int m = n;m < M;m++) {
sum += B[m];
vb.push_back(sum);
}
}
sort(vb.begin(), vb.end());
int vbsize = vb.size();
long long ans = 0;
for (int n = 0;n < N;n++) {
int sum = 0;
for (int m = n;m < N;m++) {
sum += A[m];
int t = T - sum;
ans += (upper_bound(vb.begin(), vb.end(), t) - vb.begin()) -
(lower_bound(vb.begin(), vb.end(), t) - vb.begin());
}
}
printf("%lld\n", ans);
return 0;
}
| cs |
바로 구할 수 있다.
#include <cstdio>
#include <vector>
#include <algorithm>
using namespace std;
int T;
int N, M;
int A[1001], B[1001];
vector<int> va, vb;
long long ans;
int main() {
scanf("%d", &T);
scanf("%d", &N);
for (int n = 0;n < N;n++) scanf("%d", &A[n]);
scanf("%d", &M);
for (int n = 0;n < M;n++) scanf("%d", &B[n]);
for (int n = 0;n < N;n++) {
int sum = 0;
for (int m = n;m < N;m++) {
sum += A[m];
va.push_back(sum);
}
}
for (int n = 0;n < M;n++) {
int sum = 0;
for (int m = n;m < M;m++) {
sum += B[m];
vb.push_back(sum);
}
}
sort(va.begin(), va.end());
sort(vb.begin(), vb.end());
int l = 0, r = vb.size() - 1;
int asize = va.size();
while(1){
if (va[l] + vb[r] == T) {
long long acnt = 1, bcnt = 1;
int ll = l, rr = r;
while (ll + 1 < asize && va[ll + 1] == va[ll]) acnt++, ll++;
while (rr - 1 >= 0 && vb[rr - 1] == vb[rr]) bcnt++, rr--;
ans += acnt*bcnt;
l = ll + 1;
r = rr;
}
if (l < asize && r >= 0 && va[l] + vb[r] < T)
l++;
if (l < asize && r >= 0 && va[l] + vb[r] > T)
r--;
if (l >= asize || r < 0) break;
}
printf("%lld\n", ans);
return 0;
}
| cs |
댓글 없음:
댓글 쓰기