[백준] 11659번 구간 합 구하기 4 C언어

[실버 3]  11659  :  구간 합 구하기 4

 

[알고리즘 분류]

누적 합

 

1 초

256 MB

63347

26884

20513

40.662%

 

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

[접근법]

일단 입력받는 정수 개수가 최대 10만 개, 그리고 합을 구해야 하는 연산 횟수가 최대 10만 개 들어올 수 있기에, 반복문을 많이 쓰면 시간 안에 풀 수가 없다. 

"누적 합(prefix sum)" 이란 어떤 배열의 원소들의 구간 합을 하나의 배열로 저장해 놓는 것을 의미한다. 실제로 누적 합을 구하게 되면, 배열을 만드는 시간 복잡도는 O(N)이 되는데, 누적 합 배열을 만드는 연산만 지나면, 나머지 연산은 상수 시간으로 처리할 수 있다. 예를 들어 10~20번째 원소의 합을 찾고자 한다면, 누적합 배열 20번째 칸에서 10번째 칸의 값을 뺀 값이 답이 될 것이다.

 

[풀이]

#include <stdio.h>
#include <stdlib.h>

int main()
{
    int n, m;
    int temp;
    int *arr;
    int start, end;
    int result;

    scanf("%d %d", &n, &m);
    arr = (int *)malloc(sizeof(int) * n);
    scanf("%d", &arr[0]);
    for (int i = 1; i < n; i++)
    {
        scanf("%d", &temp);
        arr[i] = arr[i - 1] + temp;
    }
    for (int i = 0; i < m; i++)
    {
        scanf("%d %d", &start, &end);
        if (start == 1)
        {
            result = arr[end - 1];
        }
        else
        {
            result = arr[end - 1] - arr[start - 2];
        }
        printf("%d\n", result);
    }
}