배열과 리스트: 구간합 구하기2 (백준 11660)

 

11660번: 구간 합 구하기 5

 

 

 

 

난이도: 실버 1

풀이: 역시 구간합 array를 새로 지정해준 후 이후 연산을 구간합 array로 진행하면 훨씬 더 빠르게 연산을 수행할 수 있다. 

 

 

 

import java.util.*;
import java.io.*;
 
public class P11660 {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        
        int A         = Integer.parseInt(st.nextToken());
        int B         = Integer.parseInt(st.nextToken());
        
        int arr[][]    = new int[A+1][A+1];
        for (int i = 1; i <= A; i++) {
            st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= A; j++) {
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        
        int arr2[][] = new int[A+1][A+1];
        for (int i = 1; i <= A; i++) {
            for (int j = 1; j <= A; j++) {
                arr2[i][j] = arr2[i-1][j] + arr2[i][j-1] - arr2[i-1][j-1] + arr[i][j];
            }
        }
        
        
        int sum;
        int x1;
        int y1;
        int x2;
        int y2;
        
        for (int i = 1; i <= B; i++) {
            st        = new StringTokenizer(br.readLine());
            x1     = Integer.parseInt(st.nextToken());
            y1        = Integer.parseInt(st.nextToken());
            x2        = Integer.parseInt(st.nextToken());
            y2        = Integer.parseInt(st.nextToken());
            
            sum    = arr2[x2][y2] - arr2[x1-1][y2] - arr2[x2][y1-1] + arr2[x1-1][y1-1];
            System.out.println(sum);
        }
    }
}