https://www.acmicpc.net/problem/11660
2차원 구간합은 원점으로부터의 사각형의 합을 이용한다.
import java.util.*;
import java.io.*;
public class Main
{
static int[][] map;
static int[][] plusmap;
static int n;
public static void pre(){
for(int i =1; i<n+1; i++){
for(int j=1; j<n+1;j++){
plusmap[i][j] = plusmap[i-1][j]+plusmap[i][j-1]-plusmap[i-1][j-1]+map[i-1][j-1]; ;
}
}
}
public static int calc(int x1, int y1, int x2, int y2){
int ans = plusmap[x2][y2]-plusmap[x1-1][y2]-plusmap[x2][y1-1]+plusmap[x1-1][y1-1];
return ans ;
}
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
String[] input1 = br.readLine().split(" ");
n = Integer.valueOf(input1[0]);
int m = Integer.valueOf(input1[1]);
map = new int[n][n];
plusmap = new int[n+1][n+1];
for(int i =0; i<n;i++){
String[] temp = br.readLine().split(" ");
for(int j=0;j<n;j++){
map[i][j] = Integer.valueOf(temp[j]);
}
}
pre();
for(int i=0; i< m;i++){
String[] temp = br.readLine().split(" ");
bw.write(calc(Integer.valueOf(temp[0])
,Integer.valueOf(temp[1])
,Integer.valueOf(temp[2])
,Integer.valueOf(temp[3]))+"\n");
}
bw.flush();
}
}
'Problem Solving > 구간합' 카테고리의 다른 글
BOJ2295 세 수의 합 (1) | 2024.02.14 |
---|---|
BOJ17232 생명게임* (1) | 2024.02.11 |
BOJ 19951 태상이의 훈련소 생활 (0) | 2024.02.09 |
BOJ16713 Generic Queries (0) | 2024.02.08 |
구간 합 구하기 개념 (0) | 2024.02.08 |