백준 11441번 : 합 구하기

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

1. 문제

N개의 수 A1, A2, ..., AN이 입력으로 주어진다. 총 M개의 구간 i, j가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

2. 알고리즘

키워드 - 부분 합

최초의 입력 받은 배열은 위 처럼 10, 20, 30, 40, 50 으로 이루어 져있는 배열이다.

배열의 부분합을 만들기 위해 0 번째 배열을 추가하고 배열[i-1] + 배열[i] 부분 합을 구한다.

문제 에서 1번과 4번 배열의 합을 구하라고 나와 있다. 1번 부터 N 까지는 모두 계산이 되어 있음으로 위와 같이 답을 도출 할 수 있다.

두번 째 예제에서는 2번 부터 4 까지의 합을 계산 해야 한다.

2번 의 부분합은 30 임으로 1번의 값을 제외해야 한다.

세번 째 예제에서는 3번부터 5번 까지의 합을 계산 해야 한다.

3번의 부분합은 60 임으로 2번 부분합을 제외 해야 한다.

마찬 가지로 나머지도 동일 하다.

3. 코드

#include <iostream>

#include <sstream>

#include <string>

#include <algorithm>

#include <functional>

#include <vector>

#include <list>

#include <queue>

#include <map>

using namespace std;

 

// 상 하 좌 우 

int dy[] = { 0, -1, 1, 0};

int dx[] = { -1, 0, 0, 1};

 

int main() {

 

    std::ios::sync_with_stdio(false); cin.tie(0);

 

    int n; cin >> n;

 

    vector<int> arr(n+1);

    arr[0] = 0;

    cin >> arr[1];

    for(int i=2; i<n+1; i++) {

        int d; cin >> d;

        arr[i] = arr[i-1] + d;

    }

    int m; cin >> m;

 

    while(m--) {

        int i,j; cin >> i >> j;

 

        int sol = arr[j] - arr[i-1];

 

        cout << sol << "\n";

    }

    return 0;

}