[BOJ] 2143 / 두 배열의 합 / Python 파이썬

[BOJ] 2143 / 두 배열의 합 / Python 파이썬

[BOJ] 2143 / 두 배열의 합 / Python 파이썬

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

2143번: 두 배열의 합

 

 

풀이

두 배열의 부분 배열의 합이 T 가 되는 경우의 수를 구하는 문제이다.

 

배열 A와 B 의 부분 배열의 합은 각각 구하여 이분탐색으로 경우의 수를 줄였고, 배열의 합을 탐색하는 방법은 두 포인터를 이용하였다.

 

T = int(input())

N = int(input())
n_list = list(map(int, input().split()))

check = {}

for i in range(N):
    tmp = n_list[i]
    if tmp not in check:
        check[tmp] = 1
    else:
        check[tmp] += 1
    for j in range(i+1, N):
        tmp += n_list[j]
        if tmp not in check:
            check[tmp] = 1
        else:
            check[tmp] += 1


M = int(input())
m_list = list(map(int, input().split()))

res = 0

for i in range(M):
    tmp = m_list[i]
    if T-tmp in check:
        res += check[T-tmp]
    for j in range(i+1, M):
        tmp += m_list[j]

        if T-tmp in check:
            res += check[T-tmp]

print(res)