백준 2143 - 두배열의 합

출처 : 2143번: 두 배열의 합 (acmicpc.net)

2143번: 두 배열의 합

 

---

두 배열의 합 성공출처분류

시간제한 메모리 제한 제출 정답 맞은 사람 정답 비율

2 초

64 MB

10031

3039

1972

28.538%

문제

한 배열 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을 출력한다.

 

---

 

[ 문제 설명 ]

 

이전 포스팅과 원리는 같습니다. 다만 여기서는 defaultdic을 이용했습죠.

참고 : 백준 2632번 - 피자 판매 (tistory.com)

백준 2632번 - 피자판매

 

for i in range(n):
    for j in range(i, n):
        print(sum(a[i: j + 1]))
        a_sum[sum(a[i:j + 1])] += 1

위의 코드를 이용하여 a 배열에서 나올 수 있는 합의 양을 구한 것 반대도 마찬가지 원리로 구합니다.

 

for key in a_sum.keys():
    answer += b_sum[target - key] * a_sum[key]

key값 중에서 b_sum [target - key] * a_sum [key] 이 0이 안 되는 경우는 answer += 해주던 이전 포스팅과 같은 원리로 답을 도출해냅니다.

 

---

 

[ 코드 ]

 

import sys
from collections import defaultdict

input = sys.stdin.readline

target = 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):
        print(sum(a[i: j + 1]))
        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
print(a_sum, b_sum)

for key in a_sum.keys():
    answer += b_sum[target - key] * a_sum[key]
    # print(B_sum[T - key])
#print(a_sum.keys())
print(answer)

 

---

후기

 

오 이전 포스팅보다 쉬운 문제