[BOJ] 2143번 - 두 배열의 합

[BOJ] 2143번 - 두 배열의 합

 

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

2143번: 두 배열의 합

 

알고리즘

---

해당 범위 내에서 특정 값이 있는지 여부를 확인하기 위한 이분탐색 ( 정렬 필수 )

1. A,B 각각의 경우의 수로 나타낸다.

2. B를 정렬한다.

3. A를 통해 B에서 해당되는 경우의 수가 있는지 이분탐색

4. 결과 출력

 

코드

---

#BOJ 2143번

import bisect

answer = 0
target = int(input())
len_a = int(input())
a = list(map(int,input().split()))
len_b = int(input())
b = list(map(int,input().split()))

result_a , result_b = [] , []

for i in range(len_a):
    for j in range(i,len_a) :
        result_a.append( sum(a[i:j+1]) )

for i in range(len_b):
    for j in range(i,len_b) :
        result_b.append( sum(b[i:j+1]) )

result_b.sort()

for trace_a in result_a :
    tg = target-trace_a
    answer += bisect.bisect_right(result_b,tg)-bisect.bisect_left(result_b,tg)

print(answer)