[백준] Class3-구간 합 구하기4 C++ 11659번

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

11659번: 구간 합 구하기 4

#include<iostream>	//C++, 메모리 2412kb, 시간 40ms
using namespace std;

int k[100001] = {};

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

	int n, m;	//수의 개수, 합을 구해야하는 횟수
	cin >> n >> m;
	for (int i = 1; i <= n; i++)
	{
		int a;
		cin >> a;
		k[i] += a + k[i - 1];
	}

	while (m--)
	{
		int i, j;	//합을 구해야 하는 구간 i~j
		cin >> i >> j;
		cout << k[j] - k[i - 1] << '\n';
	}

	return 0;
}

#include <stdio.h>	//C, 메모리 1500kb, 시간 64ms

int k[100001];

int main() {
	int n, m;
	int i, j;

	scanf("%d %d", &n, &m);

	for (int i = 1; i <= n; i++)
	{
		scanf("%d", &k[i]);
		k[i] += k[i - 1];
	}

	for (int p = 0; p < m; p++)
	{
		scanf("%d %d", &i, &j);
		printf("%d\n", k[j] - k[i - 1]);
	}

	return 0;
}

접근방법: 일반적으로 합을 따로 구해서 풀이로 풀면 시간초과가 나므로, 처음에 n개의 수를 입력받을 때부터 전 배열과 합한 값을 해당 배열에 저장하고 출력할 때 각 구간의 차를 출력하면 시간초과가 나지 않는다.

이러한 알고리즘을 슬라이딩 윈도우 알고리즘이라고 한다.