[백준 2167 ] 2차원 배열의 합

문제    www.acmicpc.net/problem/2167

풀이

( 1 ) DP 정의하기

dp[i][j] = (0,0) ~ (i,j) 까지 배열들의 합 

- dp[0][j] = 0

- dp[i][0] = 0

dp[0][0]
		dp[2][2]

(2) DP 입력하기

dp[i][j] = value[i][j] +  dp[i-1][j] + dp[i][j-1] + dp[i-1][j-1] 

		dp[i-1][j-1]	dp[i-1][j]
		dp[i][j-1]	dp[i][j]  (value[i][j])

(3) ( i, j ) ~ ( x, y ) 출력하기

ouput = dp[x][y] - ( dp[x][j-1] + dp[i-1][y] - dp[i-1][j-1] )  

// dp[i-1][j-1] 은 중복해서 제거되므로 다시 추가. 

( 0 , 0 )
	dp[i-1][j-1]		dp[i-1][y]
		( i , j )
	dp[x][j-1]		( x, y )  dp[x][y]
				( N , M )

코드

/*  BJ 2167 - 2차원 배열의 합 
 *  Coded by Handal ( 2019.02 )
 */
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main{
    static BufferedReader brr = new BufferedReader(new InputStreamReader(System.in));
    static StringTokenizer stt;
    public static void main(String[] args) throws IOException {
        stt = new StringTokenizer(brr.readLine());
        int N = Integer.parseInt(stt.nextToken());
        int M = Integer.parseInt(stt.nextToken());
        int[][] dp = new int[N + 1][M + 1];
        for (int i = 1; i <= N; i++) {
            stt = new StringTokenizer(brr.readLine());
            for (int j = 1; j <= M; j++)
                dp[i][j] = Integer.parseInt(stt.nextToken()) + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] ;
        }
        int K = Integer.parseInt(brr.readLine());
        while (K-- > 0) {
            stt = new StringTokenizer(brr.readLine());
            int i = Integer.parseInt(stt.nextToken());
            int j = Integer.parseInt(stt.nextToken());
            int x = Integer.parseInt(stt.nextToken());
            int y = Integer.parseInt(stt.nextToken());
            System.out.println(dp[x][y] - dp[i - 1][y] - dp[x][j - 1] + dp[i - 1][j - 1]);
        }
    }
}