[백준] 2143번 - 두 배열의 합 (파이썬)

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

# 두 배열의 합
import sys
import bisect
input = sys.stdin.readline

K = int(input())
N = int(input())
A = list(map(int, input().split()))
M = int(input())
B = list(map(int, input().split()))


sum_A = []
for i in range(N):
    sum = 0
    for j in range(i, N):
        sum += A[j]
        sum_A.append(sum)

sum_B = []
for i in range(M):
    sum = 0
    for j in range(i, M):
        sum += B[j]
        sum_B.append(sum)

result = 0
sum_B.sort()
for sum_a in sum_A:
    temp = K - sum_a
    left = bisect.bisect_left(sum_B, temp)
    right = bisect.bisect_right(sum_B, temp)
    result += right-left
print(result)

 

이진탐색, bisect

1. 입력을 받는다

2. A리스트의 부분합 sum_A와 B리스트의 부분합 sum_B를 구한다.

3. sum_B만 정렬 (bisect 사용을 위해서)

4. 목표값인 K에서 sum_A값을 뺀 값이 B리스트에 몇개가 있는지 찾는다.

    - bisect_left와 bisect_right을 이용하면 같은 수가 몇개 있는지 구할 수 있다.

    - 해당 인덱스를 뺀 값(목표하는 값의 개수) 만큼 result에 더해준다.

5. result 출력