[백준 / C언어] 11659번: 구간 합 구하기 4 (Prefix Sum 알고리즘)

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

11659번: 구간 합 구하기 4

 

난이도: solved.ac 실버 3

 

알고리즘 분류

---

누적 합

 

접근 방법

---

위의 성질을 이용한다.

 

위의 성질을 이용하면, i번째 수부터 j번째 수의 합을 S로 나타낼 수 있다.

 

따라서 아래와 같은 식이 도출된다.

 

코드

---

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

int main() {
	int N, M, i, j, temp;
	scanf("%d %d", &N, &M);
	int* sum = (int*)calloc(N + 1, sizeof(int));
	for (i = 1; i <= N; i++) {
		scanf("%d", &temp);
		sum[i] = sum[i - 1] + temp;
	}
	while (M) {
		scanf("%d %d", &i, &j);
		printf("%d\n", sum[j] - sum[i - 1]);
		M--;
	}
	return 0;
}