[백준 2143] 두 배열의 합 - 파이썬(Python)

 

 

문제

---

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

2143번: 두 배열의 합

 

나의 풀이

---

단순히 두 배열의 합을 구해 일일히 비교하면서 합이 T가 되는지 구해보는 방식은 O(n^2m^2)만큼의 시간복잡도가 걸려서 통과되지 않는다. 연산시간을 줄여야 하는데 A의 부분합에 대한 dictionary를 만든 뒤 (T-B의부분합)이 A의 부분합 dictionary 내에 있는지 파악해 가짓수에 더해주어야 한다. 이렇게 하면 딕셔너리의 원소 액세스 시간복잡도 O(1)이라는 이점을 이용해 연산 시간을 줄일 수 있다.

 

코드

---

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

import sys
input = sys.stdin.readline
from collections import defaultdict

T = int(input())
n = int(input())
A = list(map(int, input().split()))
m = int(input())
B = list(map(int, input().split()))

ans = 0
A_dict = defaultdict(int)

for i in range(n):
    for j in range(i, n):
        A_dict[sum(A[i:j+1])] += 1

for i in range(m):
    for j in range(i, m):
        ans += A_dict[T - sum(B[i:j+1])]

print(ans)