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

www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

문제 설명 : 

(x1,y1) 부터 (x2,y2) 까지 합을 구하기

 

문제 풀이 : 

1. 원래의 배열에서 각 구간을 합해준 dp 배열을 만들어줍니다.

ex)

dp 배열의 8은 3 + 3 에서 중복된 1을 뺀 뒤에, 원래 배열의 3을 더한 것 입니다.

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

dp[2][2] = dp[1][2] + dp[2][1] - dp[1][1] + 3

 

2. 이후, 만들어진 구간 합 배열에서 (x1,y1) 부터 (x2,y2) 까지의 합을 출력하기 위해

ex)

노란 부분인 2,2 부터 3,4 까지 구한다고 할 때

빨간 부분인 1,1 ~ 1,4 를 빼고 , 파란 부분인 1,1 ~ 1,3 을 빼고, 두 번 빠진 1,1 을 더하면 됩니다.

dp[x2][y2] - dp[x1-1][y2] - dp[x2][y1-1] + dp[x1-1][y1-1]

dp[3][4] - dp[1][4] - dp[3][1] + dp[1][1]

42 - 10 - 6 + 1 = 27

import java.util.Arrays;
import java.util.Scanner;

public class Main{
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		int N = sc.nextInt();
		int M = sc.nextInt();
		int[][] dp = new int[N+1][N+1];
		
		for (int i = 1; i < N+1; i++) {
			for (int j = 1; j < N+1; j++) {
				int n = sc.nextInt(); // 현재 위치 구간 
				//더한 구간 합 
				 dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + n;
				 //dp[2][2] = dp[1][2] + dp[2][1] - dp[1][1](중복) + 3(현재);
				 // 8 = 3 + 3 - 1 + 3;
			}
		}

		for(int k = 0; k < M; k++) {
			int x1 = sc.nextInt();//2
			int y1 = sc.nextInt();//2
			int x2 = sc.nextInt();//3
			int y2 = sc.nextInt();//4
			
			System.out.println(dp[x2][y2]-dp[x1-1][y2]-dp[x2][y1-1]+dp[x1-1][y1-1]);
			//dp[3][4] - dp[1][4] - dp[3][1] + dp[1][1];
		}
	}
}