C++에서 누적합 구하기

누적합은 요소들의 누적된 합의 의미로 어떠한 배열을 기반으로 앞에서부터 요소들의 누적된 합을 

저장하여 새로이 배열을 만들어 이를 활용하는 것을 말합니다.

 

 앞에서부터 더하는 prefix sum과 뒤에서부터 더하는 suffix sum 이 있지만,
코딩 테스트에서는 prefix sum만 나오니 prefix sum만 배우면 됩니다.

 

 

코드 적용하기

승철이는 뇌를 잃어버렸다.
학교에 갔더니 선생님이 자연수로 이루어진 N개의 카드를 주면서 M개의 질문을 던진다.
그 질문은 나열한 카드 중 A번째부터 B번째까지의 합을 구하는 것이다.
뇌를 잃어버렸기 때문에 승철이는 이 문제를 풀 수 없다.
문제를 풀 수 있는 프로그램을 작성해보자.

 

입력 > 수의 개수 N, 합을 구해야 하는 횟수 M, 그 이후 N개의 수가 주어진다.
수는 100 이하 자연수, 그 이후 M개의 줄에는 합을 구해야 하는 구간 A, B가 주어진다.

출력 > M개의 줄에 A부터 B까지의 합을 구하라

 

'나열한 카드 중 A번째부터 B번째까지의 합을 구하는 것'에서 누적합을 떠올릴 수 있습니다.

 

시간 복잡도를 고려하기 위해 각 변수의 범위를 먼저 확인합니다.

1 <= N <= 100,000
1 <= M <= 100,000
1 <= A <= B <= N

 

누적합을 사용하지 않고 문제를 풀게되면 다음과 같은 코드를 구현할 수 있습니다.

#include <bits/stdc++.h>
using namespace std;

int a[100004], b, c, psum[100004], n, m;

int main() {
    cin >> n >> m;
    for (int i=1; i<=n ; i++) {
        cin >> a[i];
    }

    for (int i=0 ; i<m ; i++) {
        cin >> b >> c;
        int sum = 0;
        for (int j=b ; j <= c ; j++) sum += a[j];
        cout << sum << '\n';
    }
    return 0;
}

 

이렇게 코드를 짜면 10만 X 10만 (100억) 의 시간복잡도를 가지게 됩니다.

 

따라서 아래와 같은 누적합을 사용한 풀이가 효율적인 풀이입니다.

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

int a[100004], b, c, psum[100004], n, m;

int main() {
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); \
    
    cin >> n >> m;
    for (int i=1 ; i<=n ; i++) {
        cin >> a[i];
        psum[i] = psum[i-1] + a[i];
    }

    for (int i=0 ; i<m ; i++) {
        cin >> b >> c;
        cout << psum[c] - psum[b -1] << "\n";
    }
    return 0;
}

 

누적합을 사용하게 되면 10만 X 1 시간복잡도를 가지게 됩니다.