11659: 구간 합 구하기 4

어떤 문제인가?

수 $N$이 주어졌을 때, $i$번째 수부터 $j$번째 수까지 합을 구하라.

시행착오 횟수

1번

1차 시도: TE

단순한 접근은 당연히 시간초과가 뜬다. 중간에 $O(NM)$인 구간이 있었기 때문이다.

#include <stdio.h>

int T[100001];

int main() {
    int N, M, i, j;
    scanf("%d%d", &N, &M);
    
    for(int k=0; k<N; k++)
        scanf("%d", &T[k]);
    for(int k=0; k<M; k++) {
        scanf("%d%d", &i, &j);
        int s = 0;
        for(;i<=j;i++)
            s += T[i-1];
        printf("%d\n", s);
    }
}

2차 시도: AC

그래서 구간 합을 빠르게 구하는 알고리즘을 봤다. 메모이제이션의 응용이며 수열이 한번 주어지면 그대로 남는다는 점을 이용해 미리 부분 합들을 구한 후, 이를 이용해 $i$번째 구간까지의 합과 $j$번째 구간까지의 합을 빼서 $i$~$j$번째 사이의 구간 합을 구하는 원리였다.

원리를 코드로 구현하면 다음과 같다.

#include <stdio.h>

int T[100001];

int main() {
    int N,M,i,j;
    scanf("%d%d", &N, &M);
    
    for(int k=1; k<=N; k++) {
        int t;
        scanf("%d", &t);
        T[k] = T[k-1] + t;
    }
    
    for(int k=0; k<M; k++) {
        scanf("%d%d", &i, &j);
        printf("%d\n", T[j]-T[i-1]);
    }
    return 0;
}

다른 분들의 풀이

내 풀이 원리와 매우 유사하므로 생략한다.