[백준 / BOJ] C++ 11659 구간 합 구하기 4

11659번: 구간 합 구하기 4

 

문제

https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

 

풀이

기본적인 누적합 배열을 통해 구간 합을 구하는 문제다. 누적 합 배열은 0번 인덱스의 값은 0이고 각 인덱스의 값이 현재까지 입력받은 수의 합인 배열이다.

 

예를 들어 입력받는 수가 1 2 3 4 5 라면 누적합 배열은 [0, 1, 3, 6, 10, 15]가 된다. 여기서 i번째 원소부터 j번째 원소까지의 합을 구하기 위해서는 arr[j] - arr[i-1]의 값을 출력하면 된다. i-1인 이유는 i번째 인덱스의 값은 i번째 수까지 더한 합인데 이를 빼면 구하고자 하는 값에서 i번째 수가 빠지기 때문이다. 위 배열에서 예를 들자면 2부터 4까지의 합은 9다. 4번 인덱스의 값은 10이고 2-1 = 1번 인덱스의 값은 1이므로 차는 9가 된다. 여기서 0번 인덱스가 0인 이유도 첫 번째 인덱스부터의 부분합을 구할 수 있도록 하기 위해서다.

 

 

코드

#include <bits/stdc++.h>
using namespace std;

int main() {
  ios::sync_with_stdio(false);
  cin.tie(NULL);
  int n, m, sum = 0;
  cin >> n >> m;
  vector<int> v(n + 1, 0);
  for (int i = 1, x; i <= n; i++) {
    cin >> x;
    sum += x;
    v[i] = sum;
  }
  while (m--) {
    int i, j;
    cin >> i >> j;
    cout << v[j] - v[i - 1] << '\n';
  }
  return 0;
}