[C++] BOJ 11659 - 구간 합 구하기 4

문제 : http://boj.kr/11659

티어 : 실버3

 

문제를 풀기전, $N$의 최대 크기가 10만이라는 점에 주의해야한다.

이 문제를 단순히 for문을 이용해서 $\sum_{k=i}^{j} arr[k]$를 구한다면 당연히 TLE를 받을 것이다.

($O(N · M) = O(10^{5} · 10^{5}) = O(10^{10})$)

그러면 이 문제를 어떻게 하면 최적화하여 풀 수 있을까?

바로, $\sum_{k=1}^{j} arr[k] - \sum_{k=1}^{i-1} arr[k] $ 의 값을 구한다면, 

$\sum_{k=i}^{j} arr[k]$의 값을 보다 빠르게 구할 수 있을 것이다.

 

arr[i]를 배열의 i번째 값,

sum[i]를 $\sum_{k=1}^{i} arr[k]$라고 정의하자.

sum[p] = sum[p-1] + arr[p] (단, $p>1$)를 이용하여 처음에 $O(N)$의 시간에 sum[$[1, N]$]을 구하고,

 $M$동안 $O(1)$의 시간에 sum[j]-sum[i-1]의 값을 출력해주기만 하면 된다.

따라서 $O(N+M)$에 이 문제를 풀 수 있다.

 

	int N, Q;
	cin >> N >> Q;
	for(int i=1; i<=N; i++) {
		cin >> arr[i];
	}
	for(int i=1; i<=N; i++) {
		brr[i] = arr[i] + brr[i-1];
	}
	int s, e;
	for(int i=0; i<Q; i++) {
		cin >> s >> e;
		cout << brr[e]-brr[s-1];
		cout << '\n';
	}