import sys
input = sys.stdin.readline
from bisect import bisect_left,bisect_right
T = int(input())
n = int(input())
A = [*map(int,input().split())]
m = int(input())
B = [*map(int,input().split())]
Aa = []
for i in range(n):
SUM = 0
for j in range(i,n):
SUM += A[j]
Aa.append(SUM)
Bb = []
for i in range(m):
SUM = 0
for j in range(i,m):
SUM += B[j]
Bb.append(SUM)
Bb.sort()
cnt = 0
for a in Aa:
cnt += bisect_right(Bb,T-a)-bisect_left(Bb,T-a)
print(cnt)
이 문제도 시간복잡도를 잘못 생각해서 오랫동안 풀지 못했었다.
A와 B 리스트의 길이가 최대 1000 밖에 안되므로 그냥 2중 for문을 돌려서 모든 부 배열의 합을 구하면 되는 아주 쉬운 문제였다.
요약하면
1. A,B 리스트의 모든 부 배열의 합에 대한 새로운 리스트를 만들어준다.
2. 둘 중 한 부 배열합 리스트를 sort한다.
3. 이진탐색을 이용하여 합이 T가 되는 경우의 수를 구한다.
오늘의 교훈) 입력값의 범위와 시간복잡도를 신경쓰자