알고리즘/백준

2143 두 배열의 합

아메숑 2019. 3. 10. 15:30

1. 문제



2. 코드

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
from collections import defaultdict
 
= int(input())
= int(input())
listA = list(map(int,input().split()))
= int(input())
listB = list(map(int,input().split()))
 
#딕셔너리에 0을 디폴트값으로 넣어준다.
map_a = defaultdict(lambda: 0)
 
for i in range(len(listA)):
    sub_sum = 0
    for j in range(i, len(listA)):
        sub_sum += listA[j]
        #map_a라는 딕셔너리에 sub_sum가 key이고 sub_sum값이 몇개 들어있는지 value로 나타낸다.
        map_a[sub_sum] += 1
 
ans = 0
for i in range(len(listB)):
    sub_sum = 0
    for j in range(i,len(listB)):
        sub_sum += listB[j]
        if s - sub_sum in map_a:
            ans += map_a[s-sub_sum]
#ex) map_a = {1: 2, 4: 2, 5: 1, 7: 1, 3: 2, 6: 1, 2: 1}
print(ans)
 
cs


3. 후기

이 문제의 핵심은  A의 모든 부분배열의 합을 딕셔너리에 넣고 B의 부분배열의 합을 구하면서 합계에서 그 값을 뺀값이 A의 부분배열의 합에 존재하면 존재하는 만큼 ans에 더한다.

B의 부분배열의 합을 구하면서 동시에 답을 찾는것이 핵심인것 같다.