구간합 구하기

phoenixKim·2021년 9월 13일

알고리즘 기법

목록 보기

31/72

언제 사용될까?

: 연속적인 컨테이너에서 두개의 인덱스가 주어지고, 해당 인덱스 내부 컨테이너의 합을 구하라고 하면 사용한다.

투포인터와 비슷하지만, 투포인터는 인덱스 사이의 합이 해당 조건에 일치여부를 확인하는 것이고, 구간합은 인덱스 사이 컨테이너 합을 구하는 것이다.

문제 : 백준 구간 합 구하기 4

문제로

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

첫번째 풀이

#include <iostream>

#include <vector>
using namespace std;




int main() {
	
	int n; 
	int m;
	cin >> n >> m;
	vector<int>v(n, 0);

	for (int i = 0; i < n; i++)
		cin >> v[i];

	for (int i = 0; i < m; i++)
	{
		int start, end;
		cin >> start >> end;
		int sum = 0;

		for (int j = start - 1; j < end ; j++)
		{
			sum += v[j];
		}
		cout << sum << endl;

	}

	return 0;
}

결과

그냥 합을 구해버리면 작은 범위값은 문제가 없으나,,
제한 사항에서 이므로 시간복잡도는 10만 * 10만이다.

1 ≤ N ≤ 100,000
1 ≤ M ≤ 100,000
1 ≤ i ≤ j ≤ N

-> 부분합이라는 방법을 사용하면 시간 복잡도는 10만이다!

큰돌님 유튜브 참고함!

https://blog.naver.com/jhc9639/222283814653

//다른 인덱스로 넘어가기 전에 현재의 값을 다음 인덱스의 값에 누적해놓으면,
위의 문제처럼 연속적인 컨테이너간의 합을 쉽게 구할 수가 있다.

입력 예제

1 ~ 3 까지의 합은 12
2 ~ 4까지의 합은 9
5 ~ 5까지의 합은 1
v[1] v[2] v[3] v[4] v[5]
5 4 3 2 1

dp 테이블을 만들어서 인덱스 증감할때마다 누적해 놓으면 쉽게 접근이 가능하다.
dp[1] dp[2] dp[3] dp[4] dp[5]
5 9 12 14 15
이렇게 만들고
위의 입력 처럼 1 ~ 3이라고 하면 -> dp[3]을 선택하면 된다. => 12

위의 입력 처럼 2 ~ 4라고 하면 -> dp[4] - dp[1] =? 14 - 5 => 9를 하면된다.

위의 입력 처럼 5 ~ 5라고 하면 -> dp[5] - dp[4] = 15 - 14 = 1이다.

두번째 풀이

#include <iostream>

#include <vector>
using namespace std;




int main() {
	
	int n; 
	int m;
	cin >> n >> m;
	vector<int>v(n + 1, 0);
	vector<int>dp(n + 1, 0);

	for (int i = 1; i <= n; i++)
	{
		cin >> v[i];
		dp[i] = dp[i - 1] + v[i];
	}
		
	for (int i = 0; i < m; i++)
	{
		int start, end;
		cin >> start >> end;

		cout << dp[end] - dp[start - 1] << "\n";

	}
	

	return 0;
}