[C++]누적 합 구하는 공식

누적합 구하기

#연속적인 수열이 주어지고 구간의 합을 구하는 문제들이 종종 출제된다.

 

백준 2559-수열(https://www.acmicpc.net/problem/2559) 같은 문제들이 수열의 구간 합을 요구하는 문제이다.

 

#누적합 그림

 

i = 1  ++++++(6) 누적합 ++++++(6)

i = 2  +++(3)       누적합 +++++++++(9)

i = 3  ++(1)         누적합 +++++++++++(11)

i = 4  ++(2)         누적합 +++++++++++++(13)

 

원래 값이 담긴 배열을 이용하여 누적합을 담는 배열을 생성한다. 누적합이 담긴 배열을 이용하여 구간의 합을 구할 수 있는데 만약 위 그림에서 i=2~3까지의 구간합을 구하고 싶다면 i=3의 값에서 i=1값을 빼면된다. 즉 11에서 6을 빼면 5가 나오는데 이는 위 그림에서 i=2 와 i=3의 합인 +++++(5) 와 같다.

 

 

#누적합을 구하는 코드

 

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

int temp, psum[5];//만약 4개의 입력값을 받는다면 길이가 5인 배열을 생성한다.

int main(){
//6 3 2 2 라는 입력값을 받는다고 가정한다.

	for(int i = 1; i<5; i++){//누적합은 index를 1부터 시작하는것이 좋다.
    	cin >> temp;
        psum[i] = psum[i-1] + temp;
        //이전 index의 값을 현재 값에 더해 누적합 배열을 생성한다.
	}
    //최종적으로 psum의 배열은 0 6 9 11 13로 초기화된다.
    
    int answer = 0;
    answer = psum[3] - psum[1];// 11-6 = 5
    cout << answer << "\n";
	return 0;
}

*/
5
/*

 

-위 코드를 응용하여 다양한 누적합 문제를 풀 수있다.