백준 11660번(구간 합 구하기 5)[JAVA]

풀이

2차원 배열의 구간 합 구하기 문제이다. 1차원 배열의 구간 합 구하기(구간 합 구하기 4-백준 11659번)에서와 같이, N과 M이 100,000이므로 구간 합으로 접근해야 한다.
2차원 합 배열 생성 공식 : termSum[i][j] = termSum[i][j-1] + termSum[i-1][j] - termSum[i-1][j-1] + arr[i][j]
2차원 배열의 구간 합 구하기 : termSum[x1][y1] - termSum[x1-1][y1] - termSum[x1][y1-1] + termSum[x1-1][y1-1]
이 문제에서는 Scanner를 쓰면 시간 초과가 뜨더라구요! 그래서 BufferedReader와 StringTokenizer를 사용하여 풀어야합니다!

교훈 : BufferedReader 사용을 습관화하자.

소스 코드

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

public class 구간합5 {
	public static void main(String arg[]) throws Exception{
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());
		
        //입력받은 배열
		int[][] arr = new int[n+1][n+1];
        //합 배열
		int[][] termSum = new int[n+1][n+1];
		
		for (int i = 1; i < n+1; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j < n+1; j++) {
				arr[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for (int i = 1; i < n+1; i++) {
			for (int j = 1; j < n+1; j++) {
				//합 배열 초기화
				termSum[i][j] = termSum[i-1][j] + termSum[i][j-1] - termSum[i-1][j-1] + arr[i][j];
			}
		}
		
		for (int i = 0; i < m; i++) {
			st = new StringTokenizer(br.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(termSum[x2][y2] - termSum[x2][y1-1] - termSum[x1-1][y2] + termSum[x1-1][y1-1]);
		}
		return;
	}
}

태클 감사합니다.
조언 환영입니다.