[C++] 백준 11659 : 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

백준 11659번 구간 합 구하기 4를 풀었다.

 

입력으로 받은 배열을 그대로 사용해서 구간 i부터 j까지의 합을 구하려고 하면 시간 초과가 나온다.

최악의 경우 10만개의 수를 10만번 더해야 해서 시간복잡도가 O(N^2)으로 예상된다.

따라서 누적 합을 사용해서 풀었다.

 

입력 받은 배열

index	0	1	2	3	4
value	5	4	3	2	1

 

누적 합으로 바꾼 배열

index	0	1	2	3	4
value	5	9	12	14	15

구간 i부터 j까지의 구간 합을 구하려면 array[j] - array[i-1]의 값을 계산하면 된다.

 

cin, cout 대신 scanf, printf를 사용해야 시간 초과를 피할 수 있다.

 

아래는 전체 코드입니다.

#include <iostream>
#include <stdio.h>
#include <string>
using namespace std;

int N, M;
int arr[100000];

int main() {
	cin >> N >> M;

	for (int i = 0; i < N; i++)
		scanf("%d", &arr[i]);

	for (int i = 1; i < N; i++) {
		arr[i] = arr[i] + arr[i - 1];
	}

	while (M--) {
		int a, b;
		scanf("%d", &a);
		scanf("%d", &b);
		a--;
		b--;
		printf("%d\n", arr[b] - arr[a - 1]);
	}

	return 0;
}