링크

11659 구간 합 구하기 4

문제

풀이

이 문제는 dp에 처음부터 현재 인덱스까지 차곡차곡 값을 갱신한다
예시 입력을 예로 들자면
dp[0] = 5
dp[1] = dp[0] + arr[1] -> 5 + 4 = 9
dp[2] = dp[1] + arr[2] -> 9 + 3 = 12
이런식으로 쭉 갱신하고
만약 3~5까지 갱신한다고 하면
dp[5]에 값에다가 dp[2]의 값을 빼면 3 4 5를 더한 값이 나온다.

코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] arr = br.readLine().split(" ");
        int n = Integer.parseInt(arr[0]);
        int m = Integer.parseInt(arr[1]);

        String[] numbers = br.readLine().split(" ");
        int[] dp = new int[numbers.length];

        dp[0] = Integer.parseInt(numbers[0]);
        for(int i=1;i<dp.length;i++){
            dp[i] = dp[i-1] + Integer.parseInt(numbers[i]);
        }

        for(int i=0;i<m;i++){
            arr = br.readLine().split(" ");

            int start = Integer.parseInt(arr[0]);
            int end = Integer.parseInt(arr[1]);

            if(start == end){
                System.out.println(Integer.parseInt(numbers[start-1]));
            } else if(start == 1){
                System.out.println(dp[end-1]);
            } else{
                System.out.println(dp[end-1] - dp[start-2]);
            }

        }

    }


}