https://www.acmicpc.net/problem/11659
11659번: 구간 합 구하기 4
첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j
www.acmicpc.net
이 문제는 재시도를 엄청 했다 첫번째 풀이로는 평범하게 사용하는 누적합을 사용해서 풀어보았다. 실버3이라서 확실히 이런 기초적인 코딩을 쓰지는 않았을 거 같지만 일단 해보았다. 당연히 시간초과가 발생했다. 그럼 무슨 알고리즘을 써야할까 알아보다 슬라이딩 윈도우 알고리즘이라는 기억 어딘가에 쳐박아놓은 알고리즘이 생각 났다. 이에 iostream의 cin과 cout을 stdio와 sync까지 끊고 코드를 작성하였음에도 시간초과가 발생했다. 이에 3번째에서는 iostream을 stdio.h 로 바꾸고 실행하니까 정상 적으로 실행 되었다.
#define _CRT_SECURE_NO_WARNINGS
#include <stdio.h>
using namespace std;
int N;
int M;
int arr[100001] = { 0, };
int i, j;
int main() {
int temp1, temp2;
scanf("%d %d", &N, &M);
for (int i = 1; i <= N; i++) {
scanf("%d", &arr[i]);
arr[i] = arr[i] + arr[i - 1];
}
for (int i = 0; i < M; i++) {
scanf("%d %d", &temp1, &temp2);
printf("%d\n", arr[temp2] - arr[temp1 - 1]);
}
}
이런 식으로 배열에 누적값을 저장해 줌으로서 범위를 구할 때 2 5를 입력했을 때를 예시로들면 5까지 입력한 값에서 1까지 누적된값을 빼면 2에서5의 누적값이 나온다 기존에 누적시키는 것보다 O(1)의 시간밖에 걸리지 않아 시간초과 가 발생하지 않는다.