[알고리즘][python][백준 2143]두 배열의 합

문제 링크

백준 2143 두 배열의 합 문제 링크

문제 풀이

1. listA라는 리스트에 A배열의 값을 모두 담는다.
2. listB라는 리스트에 B배열의 값을 모두 담는다.
3. dictA라는 딕셔너리를 만든다.
4. 최종 답이 될 ans 변수를 0으로 초기화 한다.
5. dictA는 key가 A배열의 부분합이고, value가 그 부분합의 수다.
   예를 들어, A배열이 1,2,3이면, 부분합은
   1 = 1
   2 = 2
   3 = 3
   1 + 2 = 3
   2 + 3 = 5
   1 + 2 + 3 = 6 처럼 나오고, 중복된거를 모으면 부분합이 1인 경우는 1번, 부분합이 2인 경우는 1번, 부분합이 3인 경우는 2번, 부분합이 5인 경우는 1번, 부분합이 6인 경우는 1번이다.
   따라서 dictA는

Key(부분합)	Value(경우의 수)
1	1
2	1
3	2
5	1
6	1

처럼 된다.

6. listB의 부분합을 구하면서, 바로 T(목표)를 만드는 경우가 있는지 확인한다.
   예를 들어 T가 5일때, listB의 부분합이 3이 나왔을 경우, listA의 부분합이 2인 경우를 찾으면 되니까 dictA의 Key값이 2인 value를 최종 답인 ans에 누적시켜 준다.

7. ans를 출력한다.

"이 문제의 포인트는 시간을 최소화 하는거다. listA의 부분합에 대한 정보를 저장한 dictA를 만드는 것처럼 listB의 부분합에 대한 정보를 저장한 dictB를 만들어서 dictA와 dictB를 일일이 하나하나 더하며 비교할수도 있지만 이는 시간 초과가 난다. 또한 이건 key값으로 바로 접근이 가능한 딕셔너리 변수의 장점을 하나도 사용하지 않은 코드가 된다."

내 코드

import sys
from _collections import defaultdict

T = int(sys.stdin.readline())

a = int(sys.stdin.readline())
listA = list(map(int, sys.stdin.readline().split()))
b = int(sys.stdin.readline())
listB = list(map(int, sys.stdin.readline().split()))

dictA = defaultdict(int)


ans = 0

for i in range(a):
    for j in range(i, a, 1):
        dictA[sum(listA[i:j+1])] += 1

for i in range(b):
    for j in range(i, b, 1):
        ans += dictA[T - sum(listB[i:j+1])]

print(ans)