백준_11660번_구간합구하기2

https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

 

import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt(); // 배열 크기 입력
		int M = sc.nextInt(); // 질의의 갯수 
		
		int arr [][] = new int[N+1][N+1]; // 숫자 배열
		int arr_x1 [] = new int [M+1];
		int arr_y1 [] = new int [M+1];
		int arr_x2 [] = new int [M+1];
		int arr_y2 [] = new int [M+1];
		
		for(int i = 1 ; i <= N ; i++) {
			
			for(int j = 1 ; j <= N ; j++) {
				
				arr[i][j] = sc.nextInt();
			}
		}
		
		// 질의 갯수만큼 입력받
		for(int c = 1; c <= M ; c++) {
			
			arr_x1[c] = sc.nextInt();
			arr_y1[c] = sc.nextInt();
			arr_x2[c] = sc.nextInt();
			arr_y2[c] = sc.nextInt();
		}
		
		int sum [] = new int [M+1];
		
		for(int q = 1 ; q <= M; q++) {
			
			for(int a = arr_x1[q]; a <= arr_x2[q]; a++) {
				for(int b = arr_y1[q]; b <= arr_y2[q]; b++) {
					
					sum[q] += arr[a][b];
				}
			}
			
		}
		
		
		for(int s = 1; s <= M ; s++) {
			
			System.out.println(sum[s]);
		}
		
	}

}

시간 초과 난 코드 ...

 

import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt(); // 배열 크기 입력
		int M = sc.nextInt(); // 질의의 갯수 
		
		int arr [][] = new int[N+1][N+1]; // 숫자 배열
		int sum [][] = new int[N+1][N+1];
		
		for(int i = 1 ; i <= N ; i++) {
			
			for(int j = 1 ; j <= N ; j++) {
				
				arr[i][j] = sc.nextInt();
			}
		}
		
		//sum배열 만들어서 값을 넣어주기  
		for(int i = 1 ; i <= N ; i++) {
			
			for(int j = 1 ; j <= N ; j++) {
				
				sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + arr[i][j];
			}
		}
		
		for(int j = 1 ; j <= M ; j++) {
			
			int result = 0;
			int x1 = sc.nextInt();
			int y1 = sc.nextInt();
			int x2 = sc.nextInt();
			int y2 = sc.nextInt();
			
			result = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
			System.out.println(result);
		}
		
		
		
	}

}

이렇게 해도 시관초과 뜸 ...

import java.util.*;

public class Main {

	public static void main(String[] args) {
		// TODO Auto-generated method stub
		
		Scanner sc = new Scanner(System.in);
		
		int N = sc.nextInt(); // 배열 크기 입력
		int M = sc.nextInt(); // 질의의 갯수 
		
		int arr [][] = new int[N+1][N+1]; // 숫자 배열
		int sum [][] = new int[N+1][N+1];
		
		for(int i = 1 ; i <= N ; i++) {
			
			for(int j = 1 ; j <= N ; j++) {
				
				arr[i][j] = sc.nextInt();
			}
		}
		
		//sum배열 만들어서 값을 넣어주기  
		for(int i = 1 ; i <= N ; i++) {
			
			for(int j = 1 ; j <= N ; j++) {
				
				sum[i][j] = sum[i][j-1] + sum[i-1][j] - sum[i-1][j-1] + arr[i][j];
			}
		}
		
		for(int j = 1 ; j <= M ; j++) {
			
			int result = 0;
			int x1 = sc.nextInt();
			int y1 = sc.nextInt();
			int x2 = sc.nextInt();
			int y2 = sc.nextInt();
			
			result = sum[x2][y2] - sum[x1-1][y2] - sum[x2][y1-1] + sum[x1-1][y1-1];
			System.out.println(result);
		}
		
		
		
	}

}