백준 11660

*실버 1단계 문제

풀이)
구간의 합을 저장하는 sum[][] 배열을 생성하여 푼다.
최대한 시간을 줄이기 위해 buffer을 사용한다.

내 코드)

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