백준11659 - 구간 합 구하기4

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

11659번: 구간 합 구하기 4

다이나믹 프로그래밍을 이용하여 풀었다. 구간의 합을 구하기 위해서 숫자의 처음부터 각 숫자의 위치까지의 모든 숫자의 합을 구하여 저장한다. 그런 다음 끝 구간까지의 합에서 구간이 처음 시작하는 직전까지의 모든 숫자 합을 뺀다. 그것을 출력하면 답이다.

#include <iostream>
#define MAX 100001
using namespace std;

int N, M; //N개의 숫자, M개의 테스트 케이스
int a, b; //a부터 b까지
int mat[MAX]; //i번째 숫자
int sum[MAX] = { 0, }; //i번째 숫자까지의 합

int main() {
    cin >> N >> M;
    for(int i = 1; i <= N; i++) { //N개의 숫자를 입력 
        scanf("%d", &mat[i]);
        sum[i] = sum[i - 1] + mat[i]; //첫번째부터 현재 숫자까지의 합을 구함
    }
    
    for(int i = 0; i < M; i++) {
        scanf("%d %d", &a, &b);
        printf("%d\n", sum[b] - sum[a - 1]) //b까지의 합에서 a - 1까지의 합을 뺀다;
    }
}