[C++] 백준 11659 구간 합 구하기 4

#include <iostream>
#include <vector>
 
int main()
{
    std::ios::sync_with_stdio(false);
    std::cin.tie(NULL);
 
    int N = 0;
    int M = 0;
    std::cin >> N >> M;
    std::vector<int> DP(N + 1);
 
    DP[0] = 0;
 
    for (int i = 1; i <= N; ++i)
    {
        int iNumber = 0;
        std::cin >> iNumber;
 
        DP[i] = DP[i - 1] + iNumber;
    }
 
    for (int i = 0; i < M; ++i)
    {
        int iFirst = 0;
        int iSecond = 0;
        std::cin >> iFirst >> iSecond;
 
        std::cout << DP[iSecond] - DP[iFirst - 1] << "\n";
    }
 
    return 0;
}

정말 아무생각 없이 더했습니다.

바로 시간초과가 나오더라구요...ㅋㅋㅋㅋ

누적 합은 DP를 통해서 풀면 됩니다.

처음부터 계속해서 더하고(DP[N])

원하는 위치까지 더한 것(DP[iSecond])에서 필요 없는 부분(DP[iFirst -1])(-1은 본인 것은 있어야하기 때문)까지 더한 것을 빼기만 하면 됩니다.