백준 11659번(구간 합 구하기 4)[JAVA]

풀이

구간 합 문제이다. 구간 합 알고리즘을 활용하려면 합 배열을 먼저 구해야한다.
합 배열은 예를 들어 S[i] = A[0] + A[1] + … + A[i] 인 배열이다. S[2] = A[0] + A[1] + A[2] 인 배열이다. 합 배열을 만드는 공식은 S[i] = S[i-1] + A[i]이다. 이러한 합 배열을 사용하지 않으면, 최악의 경우인 구간 0부터 i까지를 구할 때, 시간 복잡도가 O(N)이 나온다.
이 문제 에서는 N과 M이 100,000이므로, 최악의 경우, 문제의 시간 제한인 1초(약 1억회 이상의 연산)를 초과하게 될 수 있다. 즉, 합 배열을 만들어서 미리 저장해놓고, 구간이 입력될 때마다 S[구간의 큰값] - S[구간의 작은값-1]로 구간 합을 합 배열에서 꺼내는 바로 구하는 공식으로 시간 복잡도 O(1)로 구할 수 있다.

소스 코드

import java.util.*;

public class 구간합4 {
	static int[] termSum;
	public static void main(String arg[]) {
			Scanner sc = new Scanner(System.in);
			int n = sc.nextInt();
			int m = sc.nextInt();
			//합 배열
			termSum = new int[n+1];
			
			//합 배열 초기화
			for (int i = 1; i < n+1; i++) {
				termSum[i] = termSum[i-1] + sc.nextInt();
			}
			
			
			for (int i = 0; i < m; i++) {
				int a = sc.nextInt();
				int b = sc.nextInt();
				
				//구간 합 공식
				System.out.println(termSum[b] - termSum[a-1]);
			}
		return;
	}
}

태클 감사합니다.
조언 환영입니다.