(C++) 백준 11659번 - 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

풀이

다이나믹 프로그래밍을 사용하여 풀이하였다.

처음부터 특정 인덱스까지의 합을 배열에 저장하고, 구간 사이의 합을 구하기 위해 특정 인덱스까지의 합(sum[j-1])에서 구간에 속하지 않는 값의 합(sum[i-2])을 빼는 방식으로 구현하였다.

#include <iostream>

using namespace std;

int sum[100002];
int num[100002];
int n, m, i, j;

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

    cin >> n >> m;
    for(int i = 0; i < n; i++) cin >> num[i];
    sum[0] = num[0];
    for(int i = 1; i < n; i++){
        sum[i] = sum[i-1]+num[i];
    }
    while(m--){
        cin >> i >> j;
        if(i == 1) cout << sum[j-1] << "\n";
        else cout << sum[j-1] - sum[i-2] << "\n";
    }
}