백준(BOJ) 2143 두 배열의 합(Python)

 

 

문제 내용

 

누적 합 & 이분 탐색 문제.

두 배열의 모든 누적 합의 값을 각각 새로운 배열에 저장하고, A의 누적 합의 값에 대해 T-값을 B의 누적 합의 값이 저장된 리스트에서 이진 탐색을 통해 찾고, 개수를 센다.

파이썬의 bisect 라이브러리를 사용하면 쉽게 구할 수 있다.

 

코드는 다음과 같다.

 

# -*- coding: utf-8 -*-
import sys
from collections import deque
import heapq
import copy
from itertools import combinations
import bisect
#input=sys.stdin.readline
#sys.setrecursionlimit(100000000)

t=int(input())
n=int(input())
A=list(map(int,input().split()))
m=int(input())
B=list(map(int,input().split()))
A2=[]
B2=[]
for i in range(n):
    for j in range(i+1,n+1):
        A2.append(sum(A[i:j]))
for i in range(m):
    for j in range(i+1,m+1):
        B2.append(sum(B[i:j]))
B2.sort()
ans=0
for i in range(len(A2)):
    ans+=bisect.bisect_right(B2,t-A2[i])-bisect.bisect_left(B2,t-A2[i])
print(ans)

신촌캠프 문제.