백준 11660번: 구간 합 구하기 5

문제 설명

• https://www.acmicpc.net/problem/11660
• (x1,y1)을 시작점, (x2,y2)을 끝점으로 하는 사각형 내 숫자의 합을 구하는 문제입니다.

접근법

• padding을 넣으면 편합니다.

누적합 Board 만들기

• C까지의 누적합 = A까지의 누적합 + B까지의 누적합 - D까지의 누적합

직사각형 내 숫자의 합 구하기

• 파란 영역의 넓이 = B까지의 누적합 + C까지의 누적합 - D까지의 누적합

정답

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

public class Main {
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		st = new StringTokenizer(br.readLine());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		int[][] cumBoard = 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++) {
				cumBoard[i][j] = Integer.parseInt(st.nextToken()) + cumBoard[i-1][j] + cumBoard[i][j-1] - cumBoard[i-1][j-1];
			}
		}

		for (int m = 0; m < M; m++) {
			st = new StringTokenizer(br.readLine());
			int fromX = Integer.parseInt(st.nextToken());
			int fromY = Integer.parseInt(st.nextToken());
			int endX = Integer.parseInt(st.nextToken());
			int endY = Integer.parseInt(st.nextToken());
			
			
			int answer = cumBoard[endX][endY] - cumBoard[fromX-1][endY] - cumBoard[endX][fromY-1]+cumBoard[fromX-1][fromY-1];
			System.out.println(answer);
		}
	}
	

}