[BOJ/백준] 2143 두 배열의 합

import sys
from collections import defaultdict
def input():
    return sys.stdin.readline().rstrip()

T = int(input())

N = int(input())
A_arr = [0] + list(map(int,input().split()))

M = int(input())
B_arr = [0] +list(map(int,input().split()))


for i in range(N):
    A_arr[i+1] += A_arr[i]

for j in range(M):
    B_arr[j+1] += B_arr[j]

A_nums = defaultdict(int)
B_nums = defaultdict(int)
for i in range(1,N+1):
    for j in range(i):
        A_nums[A_arr[i] - A_arr[j]] += 1

for i in range(1,M+1):
    for j in range(i):
        B_nums[B_arr[i] - B_arr[j]] += 1

result = 0
for num in A_nums:
    find_num = T -num
    if B_nums.get(find_num):
        result = result + A_nums[num] * B_nums[find_num]

print(result)

 

이 문제는 누적합을 이용해 풀었다. 이 문제는 다음과 같다. 두 배열이 주어지고,

 

두 배열의 원소들을 더해서 T가 나올 수 있는 경우의 수를 구하는 문제이다.

 

그래서 먼저 사전 작업을 해주었다.

 

각 배열들을 전부 누적합을 통해 특정 구간의 전체 합을 구하기 쉽게 만들어줬다.

 

이렇게 누적합을 미리 준비해주고,

 

j ->i 까지의 나올수 있는 모든 종류의 부분 합을 dict 에 저장을 해준다.

 

이렇게 사전 준비 작업을 했으면,

 

A_nums 라는 A 배열에서 나올 수 있는 모든 부분 배열의 합의 종류들의 key 값으로 탐색을 해준다.

 

T 에서 A에서 나올 수 있는 배열의 합을 뺀 값이 B에 존재 하면,

 

이 두 배열의 값들로 만들 수 있는 경우의 수는 A_nums[num] * B_nums[find_num]이 된다.

 

이 값들을 구해서 결과 값을 출력해주면 된다.