알고리즘/백준
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 s = int(input()) a = int(input()) listA = list(map(int,input().split())) b = 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의 부분배열의 합을 구하면서 동시에 답을 찾는것이 핵심인것 같다.