[알고리즘][Python] 백준 2143 두 배열의 합 문제 풀이

문제 출처 : www.acmicpc.net/problem/2143

2143번: 두 배열의 합

---

문제 해석 : 두 배열에 있는 부분 배열의 합이 T를 만족하느 갯수를 찾는 문제이다.

 

문제 풀이 : 배열의 부분합을 저장한 딕셔너리 자료형을 탐색하여 갯수를 카운트하면 된다.

 

풀이 시간 (기록용) : 35분 12초

 

---

풀이 코드

import sys
from collections import defaultdict

input = sys.stdin.readline

T = int(input())
N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))

A_sum = defaultdict(int)
B_sum = defaultdict(int)

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

for i in range(M):
    for j in range(i, M):
        B_sum[sum(B[i:j+1])] += 1

answer = 0

for key in A_sum.keys():
    answer += B_sum[T - key] * A_sum[key]
print(answer)

---

author : donghak park
contact : donghark03@naver.com

## 문제의 저작권은 백준 알고리즘 사이트에 있습니다. 혹시 문제가 되는 부분이 있으면 연락 바랍니다.