[알고리즘] 다이나믹프로그래밍을 활용한 구간의 합 구하기

안녕하세요, 여행벌입니다.

오늘은 간단하게 배열의 구간의 합을 쉽게 구하는 방법에 대해서 포스팅하겠습니다.

배열의 값들이 바뀐다면, 세그먼트 트리를 이용해야 하지만

배열의 값이 바뀌지 않는다면, DP를 이용해 쉽게 구간의 합을 구할 수 있습니다.

---

[배열의 합 구하기]

A[ N ] : 원소들이 N개 들어있는 배열

이때, A[ i ] ~ A[ j ]까지의 합을 여러 번 구해야 된다고 가정합시다.

먼저, 새로운 배열을 하나 정의하겠습니다.

S [ N ] : A배열의 첫번 째 원소부터 K번째 원소까지의 합을 저장한 배열. ( S[ k ] = A [0] + A [1] + ⋯ + A [k] )

그러면, A [ i ] ~ A[ j ] 까지의 합 = S[ j ] - S[ i - 1]이 성립합니다.

또, S[ K ] = S[ K - 1 ] + A[ K ]와 같은 점화식이 성립합니다.

이 두 가지 사실을 이용해 S 배열을 빠르게 채우고, S 배열의 값을 이용해 구간의 합을 구한다면,

굉장히 빠르게 구할 수 있습니다.

 

실습을 해보겠습니다.

#include<iostream>

using namespace std;

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
	
	int A[10], S[10];
	cout << "A배열의 원소를 10개 입력하시오.\n";
	for (int i = 0; i < 10; i++)
		cin >> A[i];
	S[0] = A[0];
	for (int i = 1; i < 10; i++)
		S[i] = S[i - 1] + A[i];
	cout << "완성된 S배열입니다.\n";
	for (int i = 0; i < 10; i++)
		cout << S[i] << ' ';
	cout << '\n';
}

Input
1 2 3 4 5 6 7 8 9 10

위의 코드에 Input으로 다음과 같이 입력하면, S배열은 어떻게 출력될까요?

완성된 S배열입니다.
1 3 6 10 15 21 28 36 45 55

다음과 같겠죠?

O(n) 만에 우리가 원하는 S 배열을 만들 수 있습니다!

 

만약, A 배열의 구간의 합을 M번 구해야 되는 문제가 있다면, 2중 포문을 이용해 구해준다면 O(N * M)이 될 것입니다.

하지만 S 배열을 만들어주고, S배열 값을 이용해 M번 A배열의 구간의 합을 구해준다면 O(N + M)으로

훨씬 효율적인 프로그램을 만들 수 있습니다.

---

추천 문제
https://www.acmicpc.net/problem/2003
https://www.acmicpc.net/problem/11441
https://www.acmicpc.net/problem/11659