[백준/java]- 구간 합 구하기 5

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

DP를 이용해 푼 문제이다. 

 2차원 배열 arr은 문제에서 주어진 입력으로 만든 2차원 배열이고 배열 dp는 행별로 누적합을 구한 배열로 설정한다.

그런다음, 행별로 누적합을 구한다. 

(dp[3][4]는 arr [3][1]부터 arr [3][4]까지 더한 것) 

 

import java.util.*;
import java.io.*;
public class Main {
    public static void main(String[] args) throws IOException {
        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[][] dp = new int[n+1][n+1];
        for (int i = 1; i <= n; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i][j-1] + Integer.parseInt(st.nextToken());
            }
        }
        for (int k = 1; k <= m; k++) {
            int sum = 0;
            st = new StringTokenizer(br.readLine());
            int x1 = Integer.parseInt(st.nextToken());
            int y1 = Integer.parseInt(st.nextToken());
            int x2 = Integer.parseInt(st.nextToken());
            int y2 = Integer.parseInt(st.nextToken());
            for (int i = x1; i <= x2; i++) {
                sum = sum + (dp[i][y2] - dp[i][y1-1]);
            }
            sb.append(sum + "\n");
        }
        System.out.print(sb);
    }
}