[Python 3] BOJ - 2143 "두 배열의 합"

 # 문제 링크 : https://www.acmicpc.net/problem/2143

2143번: 두 배열의 합

 # 풀이 :

투 포인터로도 풀 수 있지만, 이번 문제는 딕셔너리로 접근하였다. 왜냐하면 어떤 수 k를 만들려고 할 때, 배열 A의 부분합이 i였다면 당연히 B의 부분합은 반드시 k - i여야 하기 때문이다. 따라서, 만일 배열 A에서 i를 부분합으로 하는 쌍의 개수가 5개 였다면, 배열 B에서 k - i가 부분합을 갖는 쌍의 개수가 2개라면, k를 만들 수 있는 전체 부분합의 개수는 5 * 2 = 10개이다. 

 

 # 코드

import sys

# 입력부
t = int(sys.stdin.readline())
n = int(sys.stdin.readline())
a = list(map(int, sys.stdin.readline().split()))
m = int(sys.stdin.readline())
b = list(map(int, sys.stdin.readline().split()))

# 배열 A의 부분합을 담을 key_set
key_set = []
ans = 0

# A의 모든 쌍을 돌면서 부분합 결과를 key_set에 담는다
# 이때 만일 A의 부분합이 temp라면 temp를 key_set에 담지 않고
# B의 부분합이 t- temp가 되어야 매칭이 가능하므로 t - temp를 담아준다
for i in range(n):
    temp = a[i]
    key_set.append(t - temp)
    for j in range(i + 1, n):
        temp += a[j]
        key_set.append(t - temp)

# 사전 생성 후, 가능한 쌍들의 갯수를 저장한다
compare = dict().fromkeys(key_set,0)
for i in key_set:
    compare[i] += 1

for i in range(m):
    temp = b[i]
    # 반드시 복수개 이상으로 이루어지지 않더라도 가능한 경우가 존재하기에
    # 1개로만 이루어진 경우를 우선적으로 체크한다
    # 다만, 이때 compare에 대응되는 값이 없다면 KeyError를 리턴하므로 예외처리를 한다
    try:
        ans += compare[temp]
    except:
        pass
    # 복수개 이상으로 이루어진 부분합의 대응여부를 확인한다
    for j in range(i + 1, m):
        temp += b[j]
        try:
            ans += compare[temp]
        except:
            pass

print(ans)