#11659: 구간 합 구하기 4 [JAVA]

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

11659번: 구간 합 구하기 4

 

 

---

 

 

 

 

문제 접근

 

 

 

 

암생각 없이 그냥 풀었더니 시간 초과 났음.

 

주어진 N, M의 범위를 보면 알 수 있듯이 단순 for문 돌려서 풀면 당연히 시간 초과 남!

 

 

 

그래서 누적 합이라는 접근법으로 시간을 줄여야한당

 

 

 

 

 

누적 합은 다음과 같다.

 

 

 

 

주어진 수가 5,4,3,2,1이라고 하자. 

a 배열의 0번 인덱스는 안쓴다고 치면 누적 합을 다음과 같이 저장할 수 있다.

 

a[1]	a[2]	a[3]	a[4]	a[5]
5	5+4	5+4+3	5+4+3+2	5+4+3+2+1

 

말 그대로 a[i]에 1번째 수부터 i번째 수까지의 합을 저장하는 것

 

 

 

 

이 누적 합을 통해 구간 합을 쉽게 구할 수 있는데

 

 

 

 

만약, 3번째 수~8번째 수까지의 구간 합을 구하고 싶으면

 

8까지의 누적 합(a[8]) - 2까지의 누적합(a[2])

으로 구할 수 있다.

 

 

 

>> 즉, i번째 수부터 j번째 수까지의 누적 합은 a[j] - a[i-1]임.

 

 

 

 

 

 

 

 

코드

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {

	static StringBuilder sb;

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int[] arr = new int[n + 1];

		st = new StringTokenizer(br.readLine());
		for (int i = 1; i <= n; i++) {
			arr[i] = arr[i - 1] + Integer.parseInt(st.nextToken());
		}

		while (m-- > 0) {
			int result = 0;

			st = new StringTokenizer(br.readLine());
			int i = Integer.parseInt(st.nextToken());
			int j = Integer.parseInt(st.nextToken());

			result = arr[j] - arr[i - 1];

			System.out.println(result);
		}

	}

}