문제
한 배열 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
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
29
30
31
32
33
34
35
36
37
38
39
40
41
|
import sys
t = int(sys.stdin.readline())
n = int(sys.stdin.readline())
A = [0] + list(map(int, sys.stdin.readline().split()))
dictA = {}
m = int(sys.stdin.readline())
B = [0] + list(map(int, sys.stdin.readline().split()))
dictB = {}
sumA = [0 for _ in range(n + 1)]
for i in range(1, n + 1):
sumA[i] = sumA[i - 1] + A[i]
for j in range(1, i + 1):
key = sumA[i] - sumA[j - 1]
try:
dictA[key] += 1
except KeyError:
dictA[key] = 1
sumB = [0 for _ in range(m + 1)]
for i in range(1, m + 1):
sumB[i] = sumB[i - 1] + B[i]
for j in range(1, i + 1):
key = sumB[i] - sumB[j - 1]
try:
dictB[key] += 1
except KeyError:
dictB[key] = 1
ans = 0
for num in dictA.keys():
try:
ans += dictA[num] * dictB[t - num]
except KeyError:
continue
print(ans)
|
cs |
A배열과 B배열의 모든 부배열의 합을 구하는 데에는 누적합을 사용하고 부배열의 합의 개수를 저장하는 데에는
딕셔너리를 사용해서 해결할 수 있는 문제다.
키는 부배열의 합이고 값은 그 개수이기 때문에 dictA의 값에 대해서 dictB에서 (t - 키)에 해당하는 값이 몇개인지를
곱해서 더해주면 된다.
'백준 온라인 저지 (BOJ) 문제풀이' 카테고리의 다른 글
| 백준 온라인 저지 20943 카카오톡 (0) | 2021.03.02 |
|---|---|
| 백준 온라인 저지 20937 떡국 (0) | 2021.03.01 |
| 백준 온라인 저지 16397 탈출 (0) | 2021.02.25 |
| 백준 온라인 저지 20951 유아와 곰두리차 (0) | 2021.02.23 |
| 백준 온라인 저지 1025 제곱수 찾기 (0) | 2021.02.20 |
