이것저것 개발 블로그

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

문제)

풀이)

당연히 가장 쉬운 것은 배열을 입력받아 구간 합을 구하는 것이지만, 당연히 시간 초과가 난다.

따라서 입력을 받으면서 더해가는 방식으로 진행했다.

일차원 배열이므로 누적합을 구하는건 간단하다!

결국 구간 합을 구하기 위해선 마지막 인덱스까지 구한 누적 합 - 처음 인덱스까지 구한 누적 합으로 작성하면 된다!

원래 입력받은 배열

누적합

3 ~ 7까지 구간합

28 - 6 = 22

import java.util.Scanner;

public class Main_BJ_11659_구간합구하기4 {

	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		
		int[] arr = new int[N+1];
		//누적합 구하기
		for(int i=1; i<=N; i++) {
			arr[i] = arr[i-1] + sc.nextInt();
		}
			
		for(int i =0; i<M; i++) {
			int start = sc.nextInt();
			int end = sc.nextInt();
			System.out.println(arr[end]-arr[start-1]);
		}
		
		sc.close();

	}

}