[BOJ] 11659번 구간 합 구하기 4

링크

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

코드

import java.util.Scanner;
public class Main {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		//누적합
		int n = sc.nextInt();
		int m = sc.nextInt();
		int[] cumulatedSumArr = new int[n+1];
		for(int i = 1; i <= n; i++) { //input 받으면서 누적합 구하기
			int tmp = sc.nextInt();
			cumulatedSumArr[i] = cumulatedSumArr[i-1] + tmp;
		}
		for(int k = 0; k < m; k++) {
			int i = sc.nextInt();
			int j = sc.nextInt();
			System.out.println(cumulatedSumArr[j] - cumulatedSumArr[i-1]);
		}
		

	}

}

풀이

처음에 아래 코드처럼 모든 가능한 경우를 모두 이차원배열에 넣고 풀려고 했는데 메모리 초과가 됐다. 시간초과 혹은 메모리초과시 누적합이 효과적이라는 것을 느낌.

int[] arr= new int[n+1];
int[][] memoization = new int [n+1][n+1];
for(int i =1; i <= n; i++) {
	arr[i] = sc.nextInt();
	//대각선
	memoization[i][i]=arr[i];
	
	for(int k = 1; k < i; k++) {
		memoization[k][i]= memoization[k][i-1]+arr[i];
	}
}

for(int k = 0; k < m; k++) {
	int i = sc.nextInt();
	int j = sc.nextInt();
	System.out.println(memoization[i][j]);
}