[11659] 구간 합 구하기 4

---

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

11659번: 구간 합 구하기 4

 

누적합과 관련된 문제이다.

누적합 알고리즘 없이 for문으로 풀게 된다면 시간초과가 발생할 것이다.

 

누적합: 배열 index가 증가함에 따라, 입력 받은 수를 누적해서 더한 값을 넣고, 구간을 지정하면 그에 맞는 값을 출력함

 

 

누적합을 저장해줄 배열 X의 입력 최대 범위를 생각해보았다.

1,000이하의 수가 입력된다고 하였으므로 누적합의 최대 범위는 1,000*100,000 = 100,000,000이다.

int의 범위를 넘지 않으므로 신경 쓰지 않아도 될 듯하다.

 

 

전체 알고리즘은 코드를 보면 될 것 같다.

#include <iostream>
using namespace std;

int N, M;
int X[100001]; // index 0은 사용하지 않음
// X[i]의 최대 범위 : 1,000*100,000 = 100,000,000


int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;

	for (int i = 1; i <= N; i++)
	{
		int x;
		cin >>x;
		X[i] = X[i - 1] + x; // 누적합
	}

	for (int i = 1; i <= M; i++) {
		int x, y;
		cin >> x >> y;
		printf("%d\n", X[y] - X[x - 1]); // cout 쓰면 시간 초과
		// 겹치는 구간을 빼줌
	}

}