[백준] #11659 구간합 구하기4 - (DP)

문제

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

11659번: 구간 합 구하기 4

목표

N개가 주어졌을때 주어지는 구간의 합을 구하기

 

풀이

시간초과때문에 수를 읽을때마다 누적합을 구하는 배열을 생성함

그후 (n,m)범위가 들어오면 totalSum[m] - totalSum[n-1]연산으로 구간합을 구함

즉 (0~m) 까지의 전체합에서 (0~n-1)까지의 전체합을 빼주면됨 

 

코드

#include <iostream>
#include <vector>
#define MAX 100001

using namespace std;

int T, S;
vector<int> vect;
int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> T >> S;
    vect.resize(T);
    int tmp;
    for (int i=1; i<=T; ++i) {
        cin >> tmp;
        vect[i] = vect[i-1] + tmp;
    }

    for (int j=0; j<S; ++j) {
        int tmp1, tmp2;
        cin >> tmp1 >> tmp2;
        cout << vect[tmp2] - vect[tmp1-1] << '\n';
    }
}