[백준] 11660번: 구간 합 구하기 5 - java

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

public class Main {
	static long mod = 1000000000;

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		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 - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + Integer.parseInt(st.nextToken());
			}
		}
		for(int i =0; i<m; i++) {
			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());
			
			int answer = dp[x2][y2]-dp[x2][y1-1]-dp[x1-1][y2]+dp[x1-1][y1-1];
			System.out.println(answer);
		}

	}

}

 

dp[i][j] => (1,1) 부터 (i,j) 까지의 합을 의미한다.

1,1~n,n 까지 dp값을 갱신할 수 있다.

 

따라서 표의 값을 입력받음과 동시에 dp[i][j] 값을 갱신해주었다.

dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + 입력받은(i,j)값

그림을 그려본다면 위와 같은 점화식을 쉽게 구할 수 있다.

 

 

 

그렇다면 (x1,y1) ~ (x2,y2) 까지의 합은 어떻게 구할까?

마찬가지로 그림을 그려본다면 점화식을 비교적 쉽게 구할 수 있을 것이다.

구하고자 하는 부분 합 = dp[x2][y2] - dp[x2][y1-1] - dp[x1-1][y2] + dp[x1-1][y1-1]