구간 합 구하기 4 (feat. 백준, 11659번)

구간 합 구하기 4
https://www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 

반응형

 

// woohyeon.kim
// https://www.acmicpc.net/problem/11659
#include <iostream>
using namespace std;
int main() {
	ios::sync_with_stdio(false), cin.tie(NULL);
	register long long N, M, dp[100001] = { 0 };
	cin >> N >> M;
	for (register int i = 0; i < N; ++i)
		cin >> dp[i];
	for (register int i = N - 2; i >= 0; --i)
		dp[i] = dp[i + 1] + dp[i];
	for (register int m = 0, t1, t2; m < M; ++m) {
		cin >> t1 >> t2;
		cout << dp[t1 - 1] - dp[t2] << "\n";
	}
	return 0;
}
// *&)*@*

1. 뒤에서부터 앞으로의 합을 dp로 관리하고 문제로 주어진 범위의 차이를 빼면 됩니다.
2. 즉 N이 100이고 [1,10]의 합을 구한다고 하면, 1부터 100까지의 합 - 11부터 100까지의 합 dp간의 차이가 되게 됩니다.
3. 유의할점은 문제에 주어진 값의 범위상 자료형은 64비트를 사용해야 합니다.