[BOJ #11659] 구간 합 구하기 4

BOJ #11659, 구간 합 구하기 4 문제입니다.

 

원소 수 N개의 정수 배열이 주어졌을 때 입력된 구간의 합을 출력하면 됩니다. 프로그램 자체가 간단하지만, 일반적인 방법으로는 시간복잡도가 너무 높아 시간 내에 풀 수 없습니다. 이를 해결하기 위해서는 '누적합'을 이용하면 됩니다. 수학에서 수열을 다룰 때 급수를 이용해 a_n = s_n - s_(n - 1)과 같이 나타내는 것과 동일한 원리를 이용합니다. 이것을 알면 코드 구현은 어렵지 않게 할 수 있겠습니다! 추가적으로 더 효율적인 방식도 있고 다양한 방식이 있으니 검색을 통해 찾아보시거나 직접 떠올려 보시면 큰 도움이 될 것이라고 생각합니다.

 

간단한 코드이나 제 코드를 첨부하도록 하겠습니다.

#include <stdio.h>
#include <stdlib.h>

int main(void) {
	int N, M;
	scanf("%d %d", &N, &M);

	int *sum_list = (int *)malloc(sizeof(int) * N);

	int sum = 0;
	int tmp;
	for (int i = 0; i < N; i++) {
		scanf("%d", &tmp);
		sum += tmp;

		sum_list[i] = sum;
	}

	int a, b;
	for (int i = 0; i < M; i++) {
		scanf("%d %d", &a, &b);
		a--;
		b--;
		
		if (a == 0)
			printf("%d\n", sum_list[b]);
		else
			printf("%d\n", sum_list[b] - sum_list[a - 1]);
	}

	free(sum_list);

	return 0;
}