[백준] 2143번 : 두 배열의 합

2143번: 두 배열의 합

2143번: 두 배열의 합

🤔 문제분석

누적합 + 이분탐색 문제로 누적합의 경우의 수를 모두 구한다음에 하나의 누적합을 순회하면서 다른 하나의 누적합의 경우의 수를 정렬한뒤 이분탐색하여 값을 찾아낸다.

이분탐색을 통하여 좌측 index와 우측 index 를 구한뒤에 (우측 - 좌측)을 통하여 해당 값이 몇개가 있는지 알 수 있다.

💻 코드

import sys
import bisect
input = sys.stdin.readline

T = int(input())
n = int(input())

A = [0]*n

for i, a in enumerate(list(map(int, input().split()))):
    if i == 0:
        A[i] = a
    else:
        A[i] = A[i-1] + a
    
m = int(input())
B = [0]*m

def prefix_sum(arr, s, e):
    if s > 0:
        return arr[e] - arr[s-1]
    else:
        return arr[e]

for i, b in enumerate(list(map(int, input().split()))):
    if i == 0:
        B[i] = b
    else:
        B[i] = B[i-1] + b

new_A = []
new_B = []

for i in range(n):
    for j in range(i, n):
        new_A.append((prefix_sum(A, i, j)))

for i in range(m):
    for j in range(i, m):
        new_B.append((prefix_sum(B, i, j)))
        
new_B.sort()

cnt = 0
for num in new_A:
    left = bisect.bisect_left(new_B, T - num)
    right = bisect.bisect_right(new_B, T - num)
    cnt += right - left

print(cnt)

🎯 피드백 및 개선사항

좌측 인덱스와 우측 인덱스를 구하는과정에서 조금 헛갈린 부분이있어서 문제를 푸는데에 조금 오래걸렸다.

좌측 인덱스 구하는 방법 : T > cost 조건에서 마지막 mid을 인덱스로 지정한다.

우측 인덱스 구하는 방법 : T ≤ cost 조건에서 마지막 mid을 인덱스로 지정 한다.