[BOJ] 2143 두 배열의 합

date

Aug 23, 2023

slug

boj-0000

author

status

Public

문제 링크

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(=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]

문제풀이

이분탐색의 Upper bound - Lower bound는, 탐색하고자 하는 원소의 갯수를 나타낸다.

A와 B에 대한 먼저 N차원 부분합을 구하면서 그것에 대한 합을 SumA, SumB에 저장해준다.

그리고 그 부분 합들을 오름차순으로 정렬해준뒤에

SumA에 대한 순회를 돌면서,

목표로하는 T에서 SumA에 해당하는 것을 뺀 것을 B에서 이분탐색을 통해 찾아주는데

이떄 Upper Bound, Lower Bound를 두개 구해주고, 그것의 개수를 뺴게 되면 그것이

S를 나타내는 부분합의 개수라고 표현할 수 있다. 그것을 저장시켜 출력하면 끝

파이썬 문제풀이 코드


import bisect
T = int(input())

n = int(input())
A = list(map(int , input().split()))

m = int(input())
B = list(map(int, input().split()))

sumA, sumB = A, B

for i in range(n):
    for j in range(i+1, n):
        sumA.append(sum(A[i:j+1])) # 부분합 저장
        
for i in range(m):
    for j in range(i+1, m):
        sumB.append(sum(B[i:j+1])) # 부분합 저장
        
sumA.sort(), sumB.sort() # 부분합들을 오름차순 정렬

count = 0
for i in range(len(sumA)):
    right = bisect.bisect_right(sumB, T-sumA[i]) # upper bound
    left = bisect.bisect_left(sumB, T-sumA[i]) # lower bound 
    count += right-left # upper bound - lower bound = count
    
print(count)

시간복잡도

입력

첫째 줄에 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을 출력한다.

[BOJ] 2143 두 배열의 합

문제 링크

문제

문제풀이

입력

출력

예제 입력

예제 출력

알고리즘 분류