[백준] 두 배열의 합

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

2143번: 두 배열의 합

누적합을 활용하여 풀이하였습니다. 누적합을 사용한 이유는 A와 B 배열 각각의 구간 합을 알아야하기 때문입니다. 먼저, A에 대해 누적합을 하면서 모든 구간의 합을 a_prefix에 저장해둡니다. 그 다음 B의 모든 구간합을 구하면서 a_prefix에 저장되어 있는 값과 현재 구간합의 합이 T를 만족하면 정답이 되게 됩니다.

 

import sys
from collections import defaultdict
#sys.stdin = open("input.txt", "r")
input = sys.stdin.readline

t = int(input())

n = int(input())
A = [0] + list(map(int, input().split()))

m = int(input())
B = [0] + list(map(int, input().split()))

# A배열의 모든 구간합을 저장
a_prefix = defaultdict(int)

for i in range(1, n + 1):
    A[i] += A[i - 1]
    for j in range(0, i):
        a_prefix[A[i] - A[j]] += 1

ans = 0

# B의 구간합을 구하면서 t를 만졸할 수 있는지 확인한다.
for i in range(1, m + 1):
    B[i] += B[i - 1]
    for j in range(0, i):
        ans += a_prefix[t - (B[i] - B[j])]

print(ans)