[백준] 11660 구간 합 구하기 5 (Java)

[11660 구간 합 구하기 5]

난이도: 실버1

11660번: 구간 합 구하기 5

문제

입력

출력

---

[아이디어]

DP를 사용하여 구하면 된다.

D[x1][y1] = (1, 1)부터 (x1, y1)까지의 누적 합을 나타낸다.

보라색 부분을 구하기 위해서는 D[3][4] - D[2][4] - D[3][1] + D[2][1] 을 구하면 되다.

D[2][1]을 다시 더해주는 이유는 그 부분이 두번 빠지기 때문이다.

---

[JAVA 코드]

import java.io.*;
import java.util.*;

public class Main {

	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static StringBuilder output = new StringBuilder();
	static StringTokenizer tokens;
	
	static int N, M;
	static int [][] nums, D;

	public static void main(String[] args) throws IOException {
		tokens = new StringTokenizer(br.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		
		nums = new int [N + 1][N + 1];
		D = new int [N + 1][N + 1];
		for(int r = 1; r <= N; r++) {
			tokens = new StringTokenizer(br.readLine());
			for(int c = 1; c <= N; c++) {
				nums[r][c] = Integer.parseInt(tokens.nextToken());
			}
		}
		
		for(int r = 1; r <= N; r++) {
			for(int c = 1; c <= N; c++) {
				D[r][c] = nums[r][c] + D[r - 1][c] + D[r][c - 1] - D[r - 1][c - 1];
			}
		}
		
		for(int i = 0; i < M; i++) {
			tokens = new StringTokenizer(br.readLine());
			int x1 = Integer.parseInt(tokens.nextToken());
			int y1 = Integer.parseInt(tokens.nextToken());
			int x2 = Integer.parseInt(tokens.nextToken());
			int y2 = Integer.parseInt(tokens.nextToken());
			
			output.append((D[x2][y2] - D[x2][y1 - 1] - D[x1 - 1][y2] + D[x1 - 1][y1 - 1]) + "\n");
		}
		System.out.println(output);
	}

}