[백준 11659] 알고리즘 62일차 : 구간 합 구하기4

www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

C++ 누적합

문제 처음 보면 엥 이게 왜 실버3이지 싶은데 풀고나면 아ㅇㅇ

 

그냥 수배열 주고 일정 구간 수의 합 구하는건데 시간복잡도 때문에 그냥 합하는 식으로 구하면 시간초과나고

누적합.. 아 이 문제 분류가 누적합이구나..

입력받을때 누적합을 같이 구해서 구간 합 구할때는

sum[end] - sum[start] (단, start != 1) 로 구해야 함

 

근데도 시간초과 나서 sync랑 cin tie null 해줬어요.

끝

사실 오늘 다익스트라 풀고있었는데 인접행렬로 풀었더니 메모리 초과나서 내일 다시 짜려구요..

 

소스코드

 

#include <iostream>
using namespace std;
int sum[100001];
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    int N, I, s,e;
    cin >> N >> I;
    int num[N+1];
    for(int i = 1 ; i <= N ; i++){
        cin >> num[i];
        if(i == 1){
            sum[i] = num[i];
        }else{
            sum[i] = sum[i-1]+num[i];
        }
    }
    for(int i = 0 ; i < I ; i++){
        cin >> s >> e;
        if(s>1){
            cout << sum[e] - sum[s-1] << "\n";
        }else{
            cout << sum[e] << "\n";
        }
    }
    
    return 0;
}