[백준(BOJ)] 11659번: 구간 합 구하기 4 (C++)

구간 합 알고리즘 사용

i~j 사이 합을 반복문을 사용할 때 시간복잡도는 O(n)인데, n이 클수록 시간복잡도가 커진다.

구간 합 알고리즘은 시간복잡도가 O(1)

먼저 현재 인덱스까지의 합을 sum[]에 저장한다.

j-1까지의 총합 sum[j-1]에 j를 더하면 sum[j]이므로 sum[j] = sum[j-1] + arr[j]

만약 구간 [i,j]의 합을 구한다면 j까지의 합에서 i 이전까지의 합을 빼면 i부터 j까지의 합이므로 sum[j]-sum[i-1]으로 나타낼 수 있다.

계산의 편의를 위해 0번 인덱스는 0으로 초기화하고 사용하지 않고, 1번 인덱스부터 N까지 사용

 

#include <iostream>
#include <vector>
#include <numeric>
using namespace std; 

int main(){
    int N, M;

    scanf("%d %d", &N, &M);

    int sum[100000+1]={0,}; // 계산 편의 위해 1번 인덱스부터 값 넣고 1번부터 시작
    for(int m=0; m<N; m++) { 
        int n;
        scanf("%d", &n); 
        sum[m+1] = sum[m] + n;
    }
    //for(int m=0; m<sum.size(); m++) cout << sum[m] << endl;
    for(int m=0; m<M; m++){
        int i,j;
        scanf("%d %d", &i, &j);
        printf("%d\n", sum[j] - sum[i-1]);
    }
}

cout.tie(0)과 같은걸 사용하고 cin, cout을 사용하면 시간 초과가 나서 scanf나 printf를 사용했다.