[백준] 구간 합 구하기 4 11659 - JAVA

문제

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

11659번: 구간 합 구하기 4

 

풀이

각 index 까지의 합을 가지고 있는 dp 배열을 구한다.

예를들어, 2 3 4 5 로 입력 받았다고 한다면 dp[1] = 2, dp[2] = 5, dp[3] = 9, dp[4] = 14가 된다.

1~3까지를 구하고 싶다면 dp[3] - dp[0] 을 하면 된다.

 

코드

import java.io.*;
import java.util.*;

public class Main {	 
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();
		
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
		int arr [] = new int[n+1];
		int dp[] = new int[n+1];
		
		st= new StringTokenizer(br.readLine());
		for(int i=1;i<=n;i++) {
			arr[i] = Integer.parseInt(st.nextToken());
		}
		
		dp[1] = arr[1];
		for(int i=2;i<=n;i++) {
			dp[i] = dp[i-1] + arr[i];
		}
		
		for(int i=0;i<m;i++) {
			st= new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			
			sb.append(dp[b] - dp[a-1]).append("\n");
		}
	
		System.out.print(sb);
	}

}