[백준] 11659번 구간 합 구하기 4 C++ 문제풀이

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

11659번: 구간 합 구하기 4

문제 풀이

누적합 배열을 생성해서 구간 합 문제를 해결했다.

처음 제출했을 때 시간복잡도가 O(N)이였는데도 시간초과가 나와서 당황했다.

ios::sync_with_stdio(false);
cin.tie(nullptr);

코드를 작성해서 main안에 넣어주니 시간 초과 문제가 해결되었다.

위의 코드들에 대해서는 다음번에 자세히 설명해 볼 예정이다.

소스 코드

#include <iostream>
using namespace std;

int sum[100001] = { 0 };
int num[100001] = { 0 };

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

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

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

	for (int j = 1; j <= N; j++) {
		sum[j] = sum[j - 1] + num[j];
	}

	for (int t = 0; t < M; t++) {
		int a, b;
		cin >> a >> b;
		cout << sum[b] - sum[a - 1] << '\n';
	}
}