백준2143- python (gold 3)

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

2143번: 두 배열의 합

처음에 n개의 숫자가 나오고 m개의 숫자가 나오는데 거기 있는 것들의 합으로 t를 만드는게 목표이다. 이 문제를 보고 뭔가 동전들로 금액맞추기가 떠올랐다. 

처음에 Nlist, Mlist를 받으면 거기서 가능한 모든 조합을 정리하고 값들을 dict으로 만들어 주었다. 왜냐하면 시간복잡도가 O(1)이기에 

for문을 두번돌면서 가능한 부배열들의 합 들을 ndict에 넣어주고 key값이 이미있으면 value를 1증가시켜주었다.

마지막 answer를 구해주는 코드는 매우 짧다.

하나씩 ndict의 키값을 돌면서 만약 mkey값과 더한게 t면 answer에 그만큼 더해주는데 해당하는 value들의 곱을 더해준다. 왜냐하면

만약 키값이 4인 value가 3이라면 이 뜻은 여기안에 1,3. 2,2. 4이런식으로 존재한다는 뜻이기에 각각의 조합을 만들수 있기 때문이다. 

전체적인 시간복잡도는 ndict를 만들어주는 것에서 O(n2)이 소요된다. 

t = int(input())
n = int(input())
nlist = list(map(int,input().split()))
m = int(input())
mlist = list(map(int,input().split()))

ndict  = {}
mdict = {}
answer = 0
for i in range(n):
    for j in range(i+1, n+1):
        tmp = sum(nlist[i:j])
        if tmp in ndict:
            ndict[tmp] += 1
        else:
            ndict[tmp] = 1

for i in range(m):
    for j in range(i+1, m +1):
        tmp = sum(mlist[i:j])
        if tmp in mdict:
            mdict[tmp] += 1
        else:
            mdict[tmp] = 1
for nkey in ndict.keys():
    if t-nkey in mdict.keys():
        answer += ndict[nkey] * mdict[t-nkey]
print(answer)