[백준] 11659번. 구간 합 구하기 4

[백준] 11659번. 구간 합 구하기 4

1. 문제

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

2. 입력

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

3. 입력

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

4. 풀이

• Prefix sum을 활용했다.
  Prefix sum 참고 블로그
• 배열에 해당 인덱스의 값을 넣는 것이 아니라 누적 합을 입력한다.
• 시작점과 끝점을 입력 받아 누적 합의 끝에서 누적 합의 시작점-1을 빼준다.

5. 처음 코드와 달라진 점

• Prefix sum을 몰라서 그냥 더하는 코드로 짜서 시간 초과가 났다.

6. 코드

#include <iostream>

using namespace std;

int arr[100001];

int main(void) {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
   
    int n, m;
    cin >> n >> m;

    for (int i = 1; i <= n; i++) {
        cin >> arr[i];
        arr[i] += arr[i - 1];
    }
    for (int i = 0; i < m; i++) {
        int from, to;
        cin >> from >> to;

        cout << arr[to] - arr[from - 1]<<"\n";
    }
}