[백준 / BOJ] C++ 11441 합 구하기

11441번: 합 구하기

 

문제

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

11441번: 합 구하기

 

 

풀이

최대 10만 개의 연속된 수의 합을 구해야 한다. 따라서 입력과 동시에 모든 구간 합을 구할 수 있도록 구현이 가능한 누적 합 배열을 만들어 해결할 수 있다. 누적 합 알고리즘은 수열의 합 Sn에 대해 Sn - Sm-1 이 Am ~ An까지의 합과 같음을 이용하는 알고리즘이다.

 

 

코드

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

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