[백준] 11659번

prefix sum 알고리즘을 이용하면 된다.

최근 2일간 알고리즘 문제를 풀고 있는데 절망 스럽다.

 

알고 나면 쉬운데, 왜 생각하면 생각이 안나는 걸까.

아무튼 prefix sum알고리즘은 구간합을 구하기에 특화된듯하다

입력받을 때, 모든 구간의 1~n의 sigma 값을 인덱스에 저장하고 끝 인덱스의 값- 첫인덱스-1한의 값을 하면 구간값을 구할 수 있다.

2~5의 경우

5-1의 값으로 구할 수 있는 것

이렇게 간단하게 해결이 가능한 걸 나는 왜 이렇게 복잡하게 생각할까.

#include <functional>
#include <iostream>
#include <sstream>
#include <vector>

int main() {
    int n, m, temp, current_i, current_j;
    std::ostringstream buffer;
    std::cin >> n >> m;
    std::vector<int> arr(n+1, 0);
    arr[0] = 0;
    for (int i = 1; i <= n; i++) {
        std::cin >> temp;
        arr[i] += temp+arr[i-1];
    }

    for (int i = 0; i < m; i++) {
        std::cin >> current_i >> current_j;
        temp = arr[current_j] - arr[current_i-1];
        buffer << temp << std::endl;
    }

    std::cout <<buffer.str();
    return 0;
}