[백준 11659번/c++] 구간 합 구하기 4

알고리즘

 

• 누적 합

 

---

1차원 배열의 구간 합 계산

누적합을 이용

5 4 3 2 1이라는 수가 주어지면

1차원 vector v

• v[1]=5
• v [2]=4+v [1]=5+4=9
• v [3]=3+v [2]=3+9=12
• v [4]=2+v [3]=2+12=14
• v [5]=1+v [4]=1+14=15

즉 v[i]는 1번째에서 i번째까지의 수를 더한 값을 나타낸다.

 

v[1]	v[2]	v[3]	v[4]	v[5]
5	9	12	14	15

따라서 i번째 수부터 j번째 수까지의 합은 v[i]-v[j-1]을 계산한 값이 된다.

• v[i] 1~i번째 수의 합
• v[j-1] 1~j-1번째 수의 합

 

---

틀린 코드: 시간 초과

5 4 3 2 1을 배열에 그대로 저장하여

i번째부터 j번째 수 까지의 합을 구하는 과정을 반복문을 i부터 j까지 돌려 더하면서 구하여 시간 초과가 발생하였다.

#include <cstdio>
#include <vector>

using namespace std;

int main(){
	// freopen("input.txt", "rt", stdin);
	int n, m, i, j, a, b, sum, tmp;
	scanf("%d %d", &n, &m);
	vector<int> v(n+1);
	for(i=1; i<=n; i++){
		scanf("%d", &tmp);
		v[i]=tmp;
	}
	for(i=0; i<m; i++){
		sum=0;
		scanf("%d %d", &a, &b);
		for(j=a; j<=b; j++){
			sum+=v[j];
		}
		printf("%d\n", sum);
	}
	
	return 0;
}

 

---

맞은 코드

위에서 설명한 누적합을 이용함으로 시간 초과가 발생하지 않았다.

#include <cstdio>
#include <vector>

using namespace std;

int main(){
	// freopen("input.txt", "rt", stdin);
	int n, m, i, j, a, b, sum, tmp;
	scanf("%d %d", &n, &m);
	vector<int> v(n+1);
	for(i=1; i<=n; i++){
		scanf("%d", &tmp);
		v[i]=v[i-1]+tmp;
	}
	for(i=0; i<m; i++){
		scanf("%d %d", &a, &b);
		sum=v[b]-v[a-1];
		printf("%d\n", sum);
	}
	
	return 0;
}