[백준][C++]11659

처음에는 쉬워보였다. M까지 더해서 N-1 까지 더한걸 빼주면 되는 간단한 문제로 보였다. 이렇게 하니 당연하게도 시간초과가 나왔다.

밑의 알고리즘 분류를 보니 누적합이였다. 누적 합을 이용하였다. 배열의 각 값에 이전값들을 더한 값으로 저장하여 값을구할 때는 M에서 

N-1을 뺴주면 된다. 이렇게 하면 앞서 만든 코드보다 배열 메모리에 접촉하는 횟수가 2회로 현저히 줄어들게 된다.

#include<iostream>
#include <algorithm>
#include <stdio.h>
#include <vector>

using namespace std;



int main(){
	int N,M;
	cin >> N >> M;
	int v[100001] = { 0 };
	for (int i = 1; i < N+1; i++) {
		scanf("%d", &v[i]);
		v[i] =v[i] + v[i-1];
	}

	for (int i = 0; i < M;i++) {
		int a,b;
		scanf("%d %d", &a, &b);
		printf("%d\n", v[b] - v[a - 1]);
	}

}

여기서 처음에는 입출력을 cin,cout으로 해줬는데 또 시간초과가 났다. 그래서 scanf,printf를 사용하니 성공하였다.