[BOJ/C] 11659번 문제풀이

문제 설명

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

입력

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

출력

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

---

풀이 과정

이 문제는 이전 문제보다는 확실히 조금 쉬운것 같아서 수월하게 풀 수 있었던 것 같다.

간략하게 풀이과정을 설명하자면 다음과 같다.

i번째부터 j번째까지의 구간 합을 빠르게 구하는 방법은 우선 배열을 처음부터 누적합 형태로 바꿔놓고  sum[j] - sum[i-1]을 해주면 구할 수 있다.

#include <stdio.h>
int arr[100001];
long long sum[100001];
 
int main(void) {
    int N, M, i, j;
    long long ans;
    scanf("%d %d", &N, &M);
 
    for (int k = 1; k <= N; k++) {
        scanf("%d", &arr[k]);
        sum[k] = sum[k - 1] + arr[k];
    }
 
    while (M--) {
        scanf("%d %d", &i, &j);
        ans = sum[j] - sum[i - 1];
        printf("%lld\n", ans);
    }
 
    return 0;
}