백준 11659 구간합구하기4 c++ // dp, dp를 사용해야할때 아는방법

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

11659번: 구간 합 구하기 4

1.  dp를 사용해야할때 아는방법

완탐 : O(NM) -> 100억 ->불가능

해결 : dp, greedy를 생각하면 된다!

 

2. 전체코드

누적합이용하면 된다.

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

/*
* DP
* 1. 테이블정의
* 2. 점화식 for문
*/

/*
* 1. 테이블정의
* d[i] : d[1]~d[i]번째까지의 누적합
* 

2.점화식
d[k] = d[k-1]+num

3.초기값 정하기


*/

int d[100004];
int n,m;

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

	cin >> n>>m;
	int num;

	for (int i = 1; i <= n; ++i) {
		cin >> num;
		d[i] = d[i - 1] + num;
	}

	while (m--) {
		int a, b;
		cin >> a >> b;
		cout << d[b] - d[a-1] << "\n";
	}


	return 0;

}