[백준 2143번] 두 배열의 합 (Python3)

import sys
input = sys.stdin.readline
from bisect import bisect_left,bisect_right

T = int(input())

n = int(input())
A = [*map(int,input().split())]

m = int(input())
B = [*map(int,input().split())]

Aa = []
for i in range(n):
  SUM = 0
  for j in range(i,n):
    SUM += A[j]
    Aa.append(SUM)

Bb = []
for i in range(m):
  SUM = 0
  for j in range(i,m):
    SUM += B[j]
    Bb.append(SUM)

Bb.sort()

cnt = 0
for a in Aa:
  cnt += bisect_right(Bb,T-a)-bisect_left(Bb,T-a)

print(cnt)

 

이 문제도 시간복잡도를 잘못 생각해서 오랫동안 풀지 못했었다.

A와 B 리스트의 길이가 최대 1000 밖에 안되므로 그냥 2중 for문을 돌려서 모든 부 배열의 합을 구하면 되는 아주 쉬운 문제였다.

 

요약하면

1. A,B 리스트의 모든 부 배열의 합에 대한 새로운 리스트를 만들어준다.

2. 둘 중 한 부 배열합 리스트를 sort한다.

3. 이진탐색을 이용하여 합이 T가 되는 경우의 수를 구한다.

 

 

오늘의 교훈) 입력값의 범위와 시간복잡도를 신경쓰자