두 배열을 주고, 두 배열의 연속된 부분집합의 합이 특정 숫자 T를 만족하는 개수를 찾으란다.. T 는 -10억 ~ 10억이고 A, B 배열은 1000개 까지 있다. 각 배열의 값은 -1백만 ~ 1백만이다. 일단 배열의 부분집합수만 해도 Sigma(1000) 이니 각 50만개가 넘는다. 두 개 결합하는 경우의 수는 50만 x 50만이므로 2초 안에 불가능하므로 필요한 경우만 빠르게 찾는 것이 목표다. 나는 두 가지를 이용해서 간편하게 풀길 원했다. 1. presum 2. lower bound, upper bound 문제에서 연속된 부분집합만을 요구하므로 미리 구간합을 계산하여 가지고 있을 수 있다. 예를 들어, A 가 [1,2,3,4,5] 라면 presum = [1, 2, 3, 4, 5, 1+2, 2+3..
