[BaekJoon] 11659번 : 구간 합 구하기 4

• 이 글은 c++로 풀이를 작성하였습니다.

문제

 

예시

 

풀이

• Prefix sum 구하기 문제입니다.
• DP를 사용하면 시간복잡도 O(N)에 구할 수 있습니다.
• D[i] = D[i-1] + D[i-2] +... +D[1]

#include<iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    
    int arr[100000]={0};
    int n,m;
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>arr[i];
        arr[i]+=arr[i-1];
    }
    
    for(int i=0;i<m;i++){
        int a,b;
        cin>>a>>b;
        cout<<arr[b]-arr[a-1]<<"\n";
    }
}

• 추가로 궁금한 점이나 수정할 부분 있으면 댓글로 남겨주세요.