[백준/BOJ/C언어] 11659번 :: 부분 합 구하기 4

  문제 링크 :: https://www.acmicpc.net/problem/11659

 

---

 Solution

 

 아주 아주 기본적이고 쉬운 구간 합 문제. 부분 합을 구해 놓고 시키는 대로 구간 합을 구하면 된다. 괜히 배열의 크기를 딱 문제에 제시된 수열의 최대 크기만큼만 선언하지 말고, 한 칸만 더 선언해 준 다음에 인덱스와 주어지는 구간을 일치시키는 게 훨씬 직관적이고 편하다. 수열을 이루는 숫자는 작아도 더하면 좀 커지므로 데이터 타입을 더 큰 단위로 선언해 주는 게 좋다. 물론 이 문제에서는 100000개의 숫자가 모두 1000이고 처음부터 끝까지의 합을 구해도 int형 범위 내일 것 같긴 한데, 넘어가는 문제도 많으니까.

---

 Code

#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 i = 1; i <= N; i++) {
        scanf("%d", &arr[i]);
        sum[i] = sum[i - 1] + arr[i];
    }
 
    while (M--) {
        scanf("%d %d", &i, &j);
        ans = sum[j] - sum[i - 1];
        printf("%lld\n", ans);
    }
 
    return 0;
}

---

 Related

2019/07/27 - [코학/알고리즘] - [알고리즘] Prefix sum(구간 합)에 대해 알아보기