[백준] 11659번. 구간 합 구하기 4 (C++)

문제

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

주의사항

빠른 입출력을 위해 아래 코드를 추가해주지 않으면 시간초과 뜬당

ios_base::sync_with_stdio(false);
cout.tie(NULL);
cin.tie(NULL);

 

풀이

[DP, 누적합]

 

INPUT////////////////////////

number[i]는 number[1]부터 number[i]까지 합한 것이 된다.

 

CHECK//////////////////////

i부터j까지 합을 구하고 싶다면 

number[j] ( 0부터 j까지 합한 값) 에서

number[i-1] (0부터 i-1까지 합한 값)를 빼면 된다.

 

#include <iostream>
#include <vector>
using namespace std;
int main()
{
	ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	//INPUT//////////////////////////////////
	int N, M; cin >> N >> M;
	vector<long long>number(N+1);
	for (int i = 1; i <= N; i++) 
	{ 
		cin >> number[i];
		number[i] += number[i - 1];
	}
	//CHECK//////////////////////////////////
	for (int k = 0; k < M; k++)
	{
		int i, j; cin >> i >> j;
		cout << number[j] - number[i-1]<<"\n";
	}
}