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

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

www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

 

 문제

 수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

 

 

 입력

 첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

 

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

 

 출력

 총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

 

 

 풀이

#include <iostream>
using namespace std;

int main() {
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	
	int N, M, arr[100001]={0,};
	cin >> N >> M;
	for(int i=1;i<=N;i++){
		int a;
		cin >> a;
		arr[i] = arr[i-1] + a;
	}
	
	for(int i=0;i<M;i++){
		int a, b;
		cin >> a >> b;
		cout << arr[b] - arr[a-1] << '\n';
	}
	return 0;
}

 구현 문제는 예전에 많이 풀어봐서 새로운 유형 문제를 풀어보았다. 유명한 구간합 문제인데 개념자체는 크게 어렵지 않았다. 0~N까지의 배열에서 a~b의 합을 구하고자 할때 for문으로 직접 접근해서 합을 구하면 O(N)이 걸리지만, 구간합 알고리즘으로 0~k까지의 합을 구해놓고 0~b까지의 합에서 0~a-1까지의 합을 빼서 a~b의 합을 구하면 O(1)이 걸린다. 구간합을 계산하는데 포인트는 a~b를 구한다면 0~b에서 0~a-1을 빼야한다는 것이다.

 이 문제는 구간합 문제에서 가장 기본적인 문제였다. 앞으로 잘 기억해두자.