[백준BaekJoon]11659: 구간 합 구하기 4

문제

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

 

풀이

누적 합을 이용하면 쉽게 풀 수 있다. 

i번째까지의 모든 수의 합을 담는 배열을 만든다.

이후 구간 합을 구하면 되는데, 만약 구해야하는 구간이 3부터 5라면, 

1번 구간부터 5번 구간까지의 합을 담고 있는 arr[5] 에서 1번 구간부터 2번 구간까지의 합을 담고 있는 arr[2] 의 값을 빼주면 된다. 

 

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

int arr[100001] = { 0, };

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);

	int N, M;
	cin >> N >> M;

	for (int i = 1; i <= N; i++) {
		cin >> arr[i];
		arr[i] = arr[i] + arr[i - 1];
	}

	while (M--) {
		int i, j;
		cin >> i >> j;
		cout << arr[j] - arr[i - 1] << '\n';
	}
}

 

시간초과가 났었는데, endl 때문.... \n을 써 버릇 하자.