[백준] 구간 합 구하기 4

- 참고: www.acmicpc.net/problem/11659

11659번: 구간 합 구하기 4

 - DP 문제

 - 구간 합을 미리 저장해 놓는다면 기존 O(NM)에 시간 복잡도를 가지던 합 계산이 O(1) 안에 풀리게 된다.

   (미리 저장해 두므로)

 

 

import java.util.Scanner;

public class Solution {
    // prefix sum
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int m = sc.nextInt();
        int[] num = new int[n+1];
        for(int i = 1; i<=n; i++) {
            num[i] = sc.nextInt();
        }

        int[][] indices = new int[m][2];
        for(int j=0; j<m; j++) {
            indices[j][0] = sc.nextInt();
            indices[j][1] = sc.nextInt();
        }

        int[] dp = new int[n+1];
        dp[0] = 0;
        for(int i=1; i<=n;i++) {
            dp[i] = dp[i-1] + num[i];
        }

        int idx = 0;
        while(idx < m) {
            System.out.println(dp[indices[idx][1]] - dp[indices[idx][0]-1]);
            idx++;
        }

    }
}