[백준] 11659번 구간 합 구하기 4 C++

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

c++

#include<iostream>
using namespace std;

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    int n,m,n1,n2;
    cin >> n >> m;
    int arr[n+1];
    int prefix[n+1];


    for(int i = 1; i <= n; i++) {
        cin >> arr[i]; // 5 4 3 2 1
        prefix[i] = prefix[i-1] + arr[i];
    }

    while(m--) {
        cin >> n1 >> n2;
        cout << prefix[n2] - prefix[n1-1] << "\n";
    }
}

문제풀이

• 누적합의 대표적인 문제이다. += 배열. 하는 것이 아닌 prefix[i] = prefix[i-1] + arr[i]를 사용해서 i번째 위치까지의 누적합을 저장한다. 그리고 n1부터 n2까지의 범위를 구하기 위해 prefix[n2] - prefix[n1-1]을 해준다.

Comment

• 처음에는 += 방식으로 풀어서 시간초과가 발생했다. 누적합 개념을 알게된 후 풀었을 때도, 마지막 n1-1이 이해되지 않아서 직접 써보면서 이해할 수 있었다.