문제 바로가기
문제:
한 배열 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(-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을 출력한다.
풀이:
문제를 보면 두 배열에서 나올수 있는 누적합 들의 합이 T가 되는것을 구하면 된다
만약 A = {1,3,1,2} 에서 A[0],A[2] 를 선택해 2를 만들면 이것은 부 배열의 합이 아니다.
A와 B의 모든 누적합을 구하고 나오는 부배열의 합을 딕셔너리로 관리한후
A 부배열의 합이 3인게 있으면 B에서 부배열의 합이 2인게 찾아서 두개의 카운트를 곱해주면 갯수가 된다.
import sys
from collections import defaultdict
sys.stdin = open('/Users/song/Desktop/Python/Python/h.txt', 'r')
t = int(input())
n = int(input())
A = list(map(int, input().split()))
m = int(input())
B = list(map(int, input().split()))
Asum = [[0] * (n + 1) for _ in range(n + 1)]
BSum = [[0] * (m + 1) for _ in range(m + 1)]
Adict = defaultdict(int)
Bdict = defaultdict(int)
for i in range(1, n + 1):
for j in range(i, n + 1):
temp = Asum[i][j - 1] + A[j - 1]
Asum[i][j] = temp
Adict[temp] += 1
for i in range(1, m + 1):
for j in range(i, m + 1):
temp = BSum[i][j - 1] + B[j - 1]
BSum[i][j] = temp
Bdict[temp] += 1
res = 0
for num, count in Adict.items():
if t - num in Bdict:
res += count * Bdict[t - num]
print(res)
댓글