백준 2143 _ Python

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

2143번: 두 배열의 합

문제

---

한 배열 A[1], A[2], …, A[n]에 대해서, 부 배열은 A[i], A[i+1], …, A[j-1], A[j] (단, 1 ≤ i ≤ j ≤ n)을 말한다. 이러한 부 배열의 합은 A[i]+…+A[j]를 의미한다. 각 원소가 정수인 두 배열 A[1], …, A[n]과 B[1], …, B[m]이 주어졌을 때, A의 부 배열의 합에 B의 부 배열의 합을 더해서 T가 되는 모든 부 배열 쌍의 개수를 구하는 프로그램을 작성하시오.

예를 들어 A = {1, 3, 1, 2}, B = {1, 3, 2}, T=5인 경우, 부 배열 쌍의 개수는 다음의 7가지 경우가 있다.

T(=5) = A[1] + B[1] + B[2]
      = A[1] + A[2] + B[1]
      = A[2] + B[3]
      = A[2] + A[3] + B[1]
      = A[3] + B[1] + B[2]
      = A[3] + A[4] + B[3]
      = A[4] + B[2] 

 

입력

---

첫째 줄에 T(-1,000,000,000 ≤ T ≤ 1,000,000,000)가 주어진다. 다음 줄에는 n(1 ≤ n ≤ 1,000)이 주어지고, 그 다음 줄에 n개의 정수로 A[1], …, A[n]이 주어진다. 다음 줄에는 m(1≤m≤1,000)이 주어지고, 그 다음 줄에 m개의 정수로 B[1], …, B[m]이 주어진다. 각각의 배열 원소는 절댓값이 1,000,000을 넘지 않는 정수이다.

 

출력

---

첫째 줄에 답을 출력한다. 가능한 경우가 한 가지도 없을 경우에는 0을 출력한다.

 

 

접근법

---

1. 어차피 2개의 list n,m밖에 주어 지지 않으므로 부분수열의 갯수또한 다 구해준다.
2. 부분 합 이라해서 무턱대고 combinations을 쓰려 했다가, 연속된 합이기 때문에 그냥 for문을 중첩해서 부분합을 구현해준다.
3. 그런 다음 Counter  을 이용하여 dictionary 형태로 바꿔 준다음, 합이 T가 되는 것을 구해준다.

 

from collections import Counter

t=int(input())
n=int(input())
a = list(map(int,input().split()))
m=int(input())
b = list(map(int,input().split()))
# 여기 까지 가 주어진 조건 입력
# 그 다음부터는 데이터 처리를 실시해준다.
sum_a=[]
sum_b=[]

for i in range(n):
    sum = 0
    for j in range(i,n):
        sum += a[j]
        sum_a.append(sum)

for i in range(m):
    sum = 0
    for j in range(i,m):
        sum += b[j]
        sum_b.append(sum)
        
# 크기 순으로 배열 후, Counter 을 이용하여 sum 이 T 가 되는 녀석들을 찾아준다.
sum_a.sort()
sum_b.sort()
c = Counter(sum_b)
ans =0
for num in sum_a:
    ans += c[t-num]
print(ans)