[코테] 백준 브루트 포스 2143번 문제

2143번 : 두 배열의 합

문제 링크

https://www.acmicpc.net/problem/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(-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 = int(input())
n = int(input())
firstArr = list(map(int, input().split()))
m = int(input())
secondArr = list(map(int, input().split()))

# 첫 번째 배열의 부분배열의 합을 저장하는 딕셔너리 생성
firstSumDict = {}
for i in range(0, n) :
    for j in range(i+1, n+1) :
        key = sum(firstArr[i:j])
        if key not in firstSumDict.keys() : 
            firstSumDict[key] = 1
        else : 
            firstSumDict[key] += 1

# 두 번째 배열의 부분배열의 합을 저장하는 딕셔너리 생성
secondSumDict = {}
for i in range(0, m) :
    for j in range(i+1, m+1) :
        key = sum(secondArr[i:j])
        if key not in secondSumDict.keys() : 
            secondSumDict[key] = 1
        else : 
            secondSumDict[key] += 1

# 첫,두번째 부분배열의 합이 T인 배열쌍의 개수의 합을 출력한다.
result = 0
for firstSum in firstSumDict.keys() :
    if T-firstSum in secondSumDict.keys() :
        result += firstSumDict[firstSum] * secondSumDict[T-firstSum]

print(result)