📚 2143 - 두 배열의 합

두 배열의 합

이해

문제에서는 두 배열의 합을 더해서, T가 되는 모든 부 배열의 쌍의 개수를 구하는 프로그램을 작성하려고 하였다.
이는 순차적으로 탐색을 하며, 완전 탐색을 해야하는 상황이다.
배열의 합 : A[i] + ... + A[j] 그 사이의 합을 구하는 문제이다.

순차적으로 탐색을 하며, 사이 구간의 합을 구할 때는 딕셔너리를 사용하면 된다.

이와 같은 문제를 풀 때는, 현재 A의 합들을 딕셔너리에 저장을 한다.
key : 부 배열의 합, value : 횟수
만약에 딕셔너리에 아직 입력된 데이터가 없을 때(횟수가 0일 때는)
딕셔너리.get메서드를 사용하면 된다.

• A 결과를 딕셔너리에 저장을 한 후
• T - B가 A key에 존재한다면 갯수 만큼 +을 하면 된다.

소스

import sys

read = sys.stdin.readline

t = int(read())

n = int(read())
a = list(map(int, read().split()))
m = int(read())
b = list(map(int, read().split()))

answer = 0

dist = dict()

for i in range(n):
    cur_sum = 0
    for j in range(i, n):
        cur_sum += a[j]
        dist[cur_sum] = dist.get(cur_sum, 0) + 1

for i in range(m):
    cur_sum = 0
    for j in range(i, m):
        cur_sum += b[j]
        answer += dist.get(t-cur_sum, 0)

print(answer)