<백준> 11659번 구간 합 구하기 4 / C++ 풀이

#include <bits/stdc++.h>

using namespace std;

int n, m;
int number[100004];
int total[100004];

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

    cin >> n >> m;

    total[0] = 0;

    for (int k = 1; k <= n; k++){
        cin >> number[k];
        total[k] = total[k - 1] + number[k];
    }

    while (m--){
        int i, j;

        cin >> i >> j;
    
        cout << total[j] - total[i - 1] << '\n'; 
    }
}

중점

1. N과 M의 범위는 10000

2. 1초라는 시간 제한 존재

 

막연하게 입력을 받고 i, j에 대해서 그때 부터 합을 구한다면 시간 초과가 난다. 해당 문제의 풀이를 위해선 DP 알고리즘을 사용해야한다.

입력을 받을 때 미리 n까지의 합을 배열에 저장을 한다. 이후 저장 된 배열에서 바로 합을 출력한다. 이때 배열의 특성을 고려하여서 순서와 범위를 유의하여서 문제를 풀이하여야 한다.

 

---

 

정답 코드