백준 11659번 - 구간 합 구하기 4

 

 

 

* 문제 링크

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

 

 

 

 

문제 내용 요약

 

N 개의 수가 주어지고, i 번째부터 j 번째 수까지의 합을 출력할건데, ( 1 ≤ N ≤ 100,000 , 각 수는 1,000이하 )

 

이 i 와 j 입력이 M개 주어진다 .( 1 ≤ M ≤ 100,000 )

 

 

 

 

 

 

접근법 (일단 무작정 더해보기)

 

 

누적 합 (Prefix Sum) 의 필요성을 알아보기 위해 무작정 더해보자.

 

 

 

시간을 생각하기 위해서는 가장 tight 한 경우를 생각해야한다.

 

그리고 보통은 최대로 입력이 많을 때다.

 

100,000개의 수가 주어졌다고 해보자.

 

그리고 1번째부터 100,000번째 수까지의 합을 달라고 한다.

 

 

10만 개의 수를 다 더하자.

 

더했나? 만세!

 

1초는 무슨 0.001초도 안 걸렸을 수도 있겠는데?

 

 

자 이제 질문 하나가 끝났다.

 

또 10만 개 다 더하라네?

 

어 근데 알고보니 그 질문만 10만 개네?

 

무려 100억 번의 덧셈을 해야한다. 1초 안에 하기에는 불가능하겠네.

 

 

 

기존에 썼던 답을 또 쓰면 되는거 아닌가?

 

하지만 얍삽하게도 다른 질문으로 99,999개의 합, 99,998개의 합 이런 식으로 주어지면 어떡하지?

 

아이고 이걸 어쩌나

 

 

 

그럴 때 필요한게 누적 합(Prefix Sum) 이다.

 

 

 

 

 

누적 합 (Prefix Sum)

 

 

단순히 배열에 N개의 수를 그대로 저장하는 것이 아니라,

 

(기본적으로는) 1번째부터 i번째까지의 합을 저장하는 것이다.

 

 

그것을 저장하는 것은 별로 문제가 되지 않는다.

 

모든 합의 범위는 int 범위 내이기도 하고,

 

s[i] = s[i-1] + t (t : 새로운 입력) 으로 각 수 마다 O(1) 의 시간으로 합을 저장할 수 있다. (s[i] : 1~i번째 수의 합)

 

 

 

어? 그러면 1부터 더하는게 아니면 어떡하죠?

 

별 문제가 되지 않는다.

 

 

굳이 수식을 넣어봤다.

 

S(i, j) 는 i 번째 수부터 j 번째 수까지의 합이라고 하자.

 

그렇기 때문에, 위의 식에 의해, S(i, j) = S(1, j) - S(1, i-1),

 

저장했던 배열로 따지면, s[j] - s[i-1] 과 같다는 것을 의미한다.

 

 

굳이 최대 N 번의 덧셈을 해줄 필요없이, 각 질문당 O(1)의 시간복잡도를 가지게 되어,

 

입력의 O(N), 질문 입력과 답변의 O(M) 되어,

 

시간복잡도는 O(N+M) 이 된다.

 

각각 최대 100,000이니, 시간이 매우 여유롭게 될 것이다.

 

 

 

 

 

내 코드

#include <iostream>
using namespace std;

int pfs[100030];

int main() {
	int n,m,t;
	scanf("%d %d",&n,&m);
	for(int i=1;i<=n;i++) {
		scanf("%d",&t);
		pfs[i]=pfs[i-1]+t;
	}
	for(int i=0;i<m;i++) {
		int a,b;
		scanf("%d %d",&a,&b);
		printf("%d\n",pfs[b]-pfs[a-1]);
	}
}

옛날에 짠 코드라 pfs 라는 이름으로 배열을 만들었네