두 배열의 합 hint

5
4
1 3 1 2
3
1 3 2


ready...

a[]  -- 첫 번째 배열
b[]  -- 두 번째 배열 

s1[] -- 첫 번째 배열의 누적 값 저장
s2[] -- 두 번째 배열의 누적 값 저장 

f1[] -- 첫 번째 배열의 부분배열로 나올수 있는 수의 빈도수를 저장 
f2[] -- 두 번째 배열의 부분배열로 나올수 있는 수의 빈도수를 저장 

step1...O(n)

a[]
1 2 3 4
-------
1 3 1 2

b[]
1 2 3
-----
1 3 2

 step2... O(n)

차례대로 각 배열의 누적 값을 구합니다.

s1[]
1 2 3 4
--------
1 4 5 7

s2[]
1 2 3
-----
1 4 6

 step3. ... 이 부분에서 O(n^2) 입니다. 

a[] 배열 1 3 1 2 에서 나올수 있는 부분 수열을 보면 (여기에서 숫자는 ai 를 의미합니다.)

1           .. s1
2           .. s2 - s1
3           .. s3 - s2
4           .. s4 - s3
1+2         .. s2
2+3         .. s3 - s1
3+4         .. s4 - s2
1+2+3       .. s3
2+3+4       .. s4-s1
1+2+3+4     .. s4

즉 s4 에서 s3 ,s2 , s1,s0 을 뺀 값
   s3 에서 s2 ,s1,s0 을 뺀 값
   s2 에서 s1,s0 을 뺀 값
   s1 에서 s0 을 뺀 값 

여기에서 s0 는 0 입니다.

이 값을 f1[] 배열에 누적 시킵니다. f1[i] 는 부분배열의 i 의 가능한 횟수 입니다.

마찬가지 방법으로 f2[i] 를 구합니다.

 step4....O(t)

구하고자 하는 수가 t 이면

f1[i] * f2[t-i] 를 구하면 됩니다.