[백준] 2143 - 두 배열의 합 🍻 (Python) / 골드 3 / 2가지 풀이 (Counter, bisect)

BAEKJOON Logo

 

 

 

 

Contents

 

---

1.  문제🔥

링크: https://www.acmicpc.net/problem/2143

문제

요약하자면, 두 개의 배열 A와 B가 있다. A의 부배열과 B의 부배열의 합이 T가 되는 부배열 쌍의 개수를 구하는 문제입니다. 부배열 이란? 배열 A가 1~n까지 원소가 있을 때, (1 <= i <= j <= n) 을 만족하는 i, j에 대해, A[i] ~ A[j]까지의 합을 뜻합니다. 즉, 부배열 이란 배열의 내부에서 연속되는 원소간의 합을 의미합니다.

1) 예제 입출력❄️

예제 입출력

배열 A가 [1, 3, 1, 2] 이고, 배열 B가 [1, 3, 2] 일 때, T=5를 만족시키는 경우의 수는 아래와 같이 7가지입니다. A의 부배열과 B의 부배열의 합으로 경우의 수를 나타냈습니다.

경우의 수

2. 핵심 논리☢️

이중 for문으로 A배열을 탐색하며 모든 부배열의 합을 구하고, 다음으로 B배열을 탐색하며 모든 부배열의 합에 대해 T(타겟값)이 만족하는 경우를 찾는 게 핵심입니다.

3. 풀이 코드✅

1) Counter 이용

from collections import Counter

T = int(input()) # 부 배열의 합으로 만족되야 하는 값
n = int(input()) # 배열 A의 원소 개수
A = list(map(int,input().split())) # 배열 A
m = int(input()) # 배열 B의 원소 개수
B = list(map(int,input().split())) # 배열 B

result = 0 # 출력할 값 0으로 초기화
c = Counter() # 카운터 c 정의

for s in range(n):
    for e in range(s,n):
        c[sum(A[s:e+1])] += 1 # 배열 A의 모든 부배열의 합을 카운터에 개수로 센다
        
for s in range(m):
    for e in range(s,m):
        t = T - sum(B[s:e+1]) # 타겟 값 T에서 B의 부배열합을 뺀 값이
        result += c[t] # A의 부배열에 존재하면 result에 더해준다. 없으면 저절로 0이 나온다.
print(result)

배열 A의 모든 부 배열의 합을 탐색하며 그 합의 값을 Key로 하고, 그 개수를 값으로하는 딕셔너리(여기선 Counter로 사용)를 c로 만듭니다. 배열 B의 모든 부 배열의 합을 탐색하며, T에서 B의 부 배열합을 뺀 값이 c에 존재하면 그 값을 result에 더해나갑니다. 그리고 result를 출력합니다.

 

2) bisect 이용

import bisect

T = int(input()) # 부 배열의 합으로 만족되야 하는 값
n = int(input()) # 배열 A의 원소 개수
A = list(map(int,input().split())) # 배열 A
m = int(input()) # 배열 B의 원소 개수
B = list(map(int,input().split())) # 배열 B

result = 0 # 출력할 값 0으로 초기화
Asum,Bsum=A,B # 각 배열로 초기화
for s in range(n):
    for e in range(s+1,n):
        Asum.append(sum(A[s:e+1])) # 배열 A의 모든 부배열의 합을 추가해준다.
for s in range(m):
    for e in range(s+1,m):
        Bsum.append(sum(B[s:e+1]))# 배열 A의 모든 부배열의 합을 추가해준다.

Asum.sort();Bsum.sort()

for i in range(len(Asum)):
    l = bisect.bisect_left(Bsum, T-Asum[i])
    r = bisect.bisect_right(Bsum, T-Asum[i])
    result+=r-l
print(result)

위의 풀이와 달라진 점은, Asum, Bsum을 구할 때, 초기화를 각각 A,B배열로 해주는 부분과, for문에서 자기 자신에 대한 부분은 건너뛴다는 점입니다. Asum과 Bsum을 정렬해주고, Asum의 각 부배열의 합에 대해, Bsum에서 bisect_right에서 bisect_left를 빼주면 T가 되는 Bsum의 부배열의 합의 경우의수가 result에 for문을 돌며 더해지게 됩니다.

 

읽어주셔서 감사합니다.

다음에 더욱 유익한 글로 찾아오겠습니다.

 

* 관련 풀이 코드는 아래 깃허브 링크에 있습니다.

https://github.com/netsus/BaekJoon/blob/master/jupyter/2143_%EB%91%90_%EB%B0%B0%EC%97%B4%EC%9D%98_%ED%95%A9.ipynb

GitHub - netsus/BaekJoon: Algorithm Problem solving

Reference)
1. BAEKJOON Logo: https://www.acmicpc.net/
2. 백준 2143 두 배열의 합