[BOJ] 구간 합 구하기 5 -실버1

다이나믹 프로그래밍... 어렵다 ........
2차원으로 넘어가니까 머리가 넘 아프다 ㅠㅠ

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws NumberFormatException, 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 arr[][] = new int[N + 1][N + 1];

		for (int i = 1; i <= N; i++) {
			StringTokenizer n = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				arr[i][j] = arr[i][j - 1] + Integer.parseInt(n.nextToken());
			}
		}
		for (int i = 0; i < M; i++) {
			int sum = 0;
			StringTokenizer r = new StringTokenizer(br.readLine(), " ");
			int x1 = Integer.parseInt(r.nextToken());
			int y1 = Integer.parseInt(r.nextToken());
			int x2 = Integer.parseInt(r.nextToken());
			int y2 = Integer.parseInt(r.nextToken());
			// 줄
			for (int j = x1; j <= x2; j++) {
				sum += arr[j][y2] - arr[j][y1 - 1];
			}
			sb.append(sum+"\n");
		}
		System.out.println(sb);
	}

}