1 번째 시도

누적합 aSum[i]과 bSum[j]를 각각 구해 연산을 하면 $O(N^2 \times M^2)$으로 시간초과가 발생하기 때문에 애초에 이 방법을 시도하지는 않았다. 그래서 그 다음으로 생각한 방식이 binary search를 이용하는 것이다. aSum에 대해서는 $O(N^2)$ 연산을 하고, bSum에 대해서는 $O(MlogM)$을 수행하여 총 $O(N^2 \times MlogM)$이 걸린다. bSum은 2차원 배열로 bSum[i][j]는 i+1부터 j까지의 누적합으로 미리 값을 계산하여 저장하였다. 당연히 시간초과가 발생했다.



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18



// bSum[i][j] : i+1부터 j까지의 누적합
for (int i = 1; i <= M; i++)
	bSum[0][i] = bSum[0][i-1] + b[i]; // b[i] : i 번째 input
	

for (int i = 1; i <= M; i++)
	for (int j = i; j <= M; j++)
		bSum[i][j] = bSum[i-1][j] - b[i];
		
int cnt = 0;
for (int i = 1; i <= N; i++) {
	for (int j = 0; j < i; j++) {
		int subSum = aSum[i] - aSum[j];
		for (int k = 0; k < M; k++)
			if(bsearch(sb[k], k+1, M, T - subSum))
				cnt++;
	}
}

2 번째 시도

중복 수행을 막기 위해 map을 활용하였다. aSum[i] - aSum[j]의 모든 결과값을 aMap, bSum[i] - bSum[j]의 모든 결과값을 bMap에 넣고, 발생 횟수를 count하여 value로 저장하였다.
aMap에서 하나 뽑고, bMap에서 하나 뽑아서 총 합이 T가 되는 횟수를 세 결과를 냈다. 시간 초과가 발생했다.
아무 생각없었다. 다시 생각해보니 aMap의 공간복잡도가 $O(N^2)$이고, bMap의 공간복잡도가 $O(M^2)$이기 때문에 위와 같은 연산을 하면 $O(N^2 \times M^2)$로 더 느려지는 풀이였다…



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34



int solution() {
	for (int i = 1; i <= N; i++) {
		int sum = 0;
		for (int j = i; j <= N; j++) {
			sum += a[j];
			aMap[sum]++;
		}
	}
	
	for (int i = 1; i <= M; i++) {
		int sum = 0;
		for (int j = i; j <= M; j++) {
			sum += b[j];
			bMap[sum]++;
		}
	}
	
	int res = 0;
	map<int, int>::iterator aIt;
	for (aIt = aMap.begin(); aIt != aMap.end(); aIt++) {
		map<int, int>::iterator bIt;
		for (bIt = bMap.begin(); bIt != bMap.end(); bIt++) {
			int aSubSum = aIt->first;
			int aCnt = aIt->second;

			int bSubSum = bIt->first;
			int bCnt = bIt->second;
			if (aSubSum + bSubSum == T) {
				res += (aCnt * bCnt);
			}
		}
	}
	return res;
}

3 번째 시도

1 번째 시도의 binary search와 2번째 시도의 map을 활용하여 $O(N^2 \times logM^2)$ 복잡도의 풀이를 생각했다. aMap을 iterator로 순회하면서 bMap을 binary search로 (T - aMap 원소) 값이 있는지 찾는다. 값이 있으면 해당 값의 count와 mMap 원소의 count를 곱한 값을 총합에 더해간다. binary search에 map을 사용할 수 없으니 bMap의 데이터를 그대로 저장하는 bVec를 추가로 두었다(메모리는 그만큼 더 사용하게 되긴 한다). 정보올림피아드 문제여서 JUNGOL에 먼저 냈더니 accept를 받았다. 하지만, BOJ에서는 72%에서 wrong answer를 받았다. 계속 고민을 하다 결과를 담는 변수를 long long으로 했더니 accept를 받을 수 있었다..



1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34



ll solution() {
	for (int i = 1; i <= N; i++) {
		int sum = 0;
		for (int j = i; j <= N; j++) {
			sum += a[j];
			aMap[sum]++;
		}
	}
	for (int i = 1; i <= M; i++) {
		int sum = 0;
		for (int j = i; j <= M; j++) {
			sum += b[j];
			bMap[sum]++;
		}
	}

	map<int, int>::iterator it;
	for (it = bMap.begin(); it != bMap.end(); it++) {
		int bSubSum = it->first;
		int bCnt = it->second;
		bVec.push_back(make_pair(bSubSum, bCnt));
	}
	sort(bVec.begin(), bVec.end());

	ll res = 0;
	for (it = aMap.begin(); it != aMap.end(); it++) {
		int aSubSum = it->first;
		int aCnt = it->second;

		int ret = bsearch(T - aSubSum);
		res += ((ll)aCnt * ret);
	}
	return res;
}