[백준알고리즘] 2143번: 두 배열의 합 -Python

[백준알고리즘] 2143번: 두 배열의 합 -Python

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

2143번: 두 배열의 합

이제 이런 문제는 간단한 것 같다... 나중에 또 시간이 지나서 풀려하면 어렵겠지만..

 

문제에서 요구하는 것은 두 개의 배열 A, B에서 각각 길이가 1 이상인 연속하는 부분 수열을 뽑아 두 부분 수열의 합으로 주어진 T를 만들 수 있는 경우의 수를 구하는 것이다.

 

우선 두 배열 a, b의 모든 연속된 부분수열의 합으로 가능한 값을 찾아주었다.

모든 합의 관리를 리스트로 하기에는 입력될 수 있는 수의 범위가 너무 넓고, 반면 메모리 제한은 64MB밖에 안되기 때문에 딕셔너리를 사용해서 발생되는 연속합을 관리해주었다.

from itertools import combinations

T = int(input())
n = int(input())
a = list(map(int, input().split()))
m = int(input())
b = list(map(int, input().split()))

acm, bcm = {}, {}
for i in range(n):
    t = 0
    for j in range(i, n):
        t += a[j]
        if acm.get(t):
            acm[t] += 1
        else:
            acm[t] = 1
for i in range(m):
    t = 0
    for j in range(i, m):
        t += b[j]
        if bcm.get(t):
            bcm[t] += 1
        else:
            bcm[t] = 1

ans = 0
for _, i in enumerate(acm):
    if bcm.get(T-i):
        ans += (acm[i]*bcm[T-i])

print(ans)

 

잘못된 점이나 부족한 점 지적해주시면 감사하겠습니다