[백준] 11659번 : 구간 합 구하기 4 (C++)

11659번 : 구간 합 구하기 4

---

문제)

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

 

 

 

입력 :

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

 

 

출력 :

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

 

 

 

 

 

 

풀이)

// 11659. 구간 합 구하기 4
#include <iostream>
#include <vector>
 
using namespace std;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(0);
 
    int n, m;
    cin >> n >> m;
 
    // 원본 수열을 위한 배열
    vector<int> vec(n + 1, 0);
    // 누적합을 위한 배열
    vector<int> prefix(n + 1, 0);
 
    // 수열을 입력 받으면서 누적합을 만들어준다.
    for (int i = 1; i < n + 1; i++)
    {
        cin >> vec[i];
        prefix[i] = prefix[i - 1] + vec[i];
    }
 
    // 해당 구간의 합은 prefix[b] - prefix[a - 1]로 구할 수 있다.
    int a, b;
    for (int i = 0; i < m; i++)
    {
        cin >> a >> b;
        cout << prefix[b] - prefix[a - 1] << "\n";
    }
 
    return 0;
}

---

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

11659번: 구간 합 구하기 4