Baekjoon 백준 11659번 구간 합 구하기4

구간 합 구하기 4 성공

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
1 초	256 MB	851	385	327	47.877%

문제

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

입력

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

출력

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

예제 입력 

5 3
5 4 3 2 1
1 3
2 4
5 5

예제 출력 

12
9
1

힌트

출처

• 문제를 만든 사람: baekjoon

시간 초과 코드

#include <stdio.h>

/*

5 3

5 4 3 2 1

1 3

2 4

5 5

*/

int main(){

     

    int n, m, arr[100000]= {0, }, i, j, x, y, f, l, sum = 0;

     

    scanf("%d %d", &n, &m);

     

    for(i = 0; i < n; i++){

         

        scanf("%d", &arr[i]);

    }

         

    for(j = 0; j < m; j++){

             

        scanf("%d %d", &f, &l);

             

        for(x = f - 1; x <= l - 1; x++){

                 

            sum += arr[x];

        }

             

        printf("%d\n", sum);

        sum = 0;

    }

 

}

Prefix_Sum 출처: http://programbasic.tistory.com/259

#include <stdio.h>

int main(){ 

int i, n, m, start, end, ans;

  int a[100000];

  int sum[100000];

  scanf("%d %d", &n, &m);

 

  for(i = 0; i < n ; i++) {

      scanf("%d",&a[i]);

     

if (i == 0)

        sum[i] = a[i]; 

      else

        sum[i] = sum[i-1] + a[i];

  }

 

for(i = 0; i < m ; i++){ 

 

  scanf("%d %d",&start,&end);

  

if (start == 1)

      ans = sum[end-1]; 

  else

      ans = sum[end-1] - sum[start-2];

  

printf("%d\n",ans);

}

}