[BOJ / C++] 구간 합 구하기 4 (다이나믹 프로그래밍, prefix sum)

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

 

1. 코드

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

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

    int n, m; 
    cin >> n >> m;

    vector<int> arr(n+1, 0);
    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
    }

    vector<int> d(n+1, 0);
    d[1] = arr[1];
    for (int i = 2; i <= n; i++) {
        d[i] = d[i-1] + arr[i];
    }

    while (m--) {
        int i, j;
        cin >> i >> j;
        cout << d[j] - d[i-1] << '\n';
    }
}

 

 

2. 분석

1. dp 테이블 정의:

i번째까지 수열의 누적합을 저장한다.

 

2. 점화식:

d[i] = d[i-1] + arr[i];

 

이러한 방식을 prefix sum이라고 한다. prefix sum을 통해 구간 합을 계산하면 dp 테이블 계산에 O(n) 구간합 계산에 O(1)이 걸려 시간복잡도 O(n)에 구간합을 구할 수 있다. 구간합은 d[i] - d[j-1]로 계산 가능하다.

 

3. 시간복잡도

시간복잡도는 단순히 생각하면 O(nm)인데 10^5 * 10^5 = 10^10 > 10^8 이므로 시간초과 판정이 나게된다. 따라서 구간 합을 계산하는 것의 시간복잡도를 떨어뜨려야하고 위 방법처럼 prefix sum을 이용하면 시간복잡도 O(n)에 계산이 가능하다. 10^5 < 10^8 이므로 시간제한 1초 이내에 통과 가능하다.