[백준] 11660 : 구간 합 구하기 5 - JAVA

시간복잡도 분석

합을 구해야하는 횟수 최악의 경우가 100,000이므로 각각 합을 매번 구한다면 1024*1024의 배열을 10만번 순회하게 될 것이다.
시간제한이 1초이므로, 구간합을 이용해야한다!

1차원 구간 합 배열만 다루었었는데, 2차원으로 확장된 것으로 생각하여 구간 합 배열을 어떻게 구성할지 고민하는게 문제의 핵심이다!

슈도코드

N, M 입력받기
A배열 선언 //원본
S배열 선언 // 구간합

for(row = 1~N만큼 반복) {
	배열의 한 행 입력받기
    for(column = 1~N만큼 반복) {
    	배열A 값 채워넣기
	}
}

//구간합 구하기
for(row를 1~N만큼 반복) {
	for(column 1~N만큼 반복) {
    	S[row][column] = S[row-1][column] + S[row][column-1] - S[row-1][column-1] + A[row][column]
    }
}

for(M만큼 반복) {
	입력받기
    x1 선언
    y1 선언
    x2 선언
    y2 선언
    출력 : S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]
}

제출 코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
import java.io.IOException;

public class Main {
	static int[][] A;
	static long[][] S;

	public static void main(String[] args) throws IOException {
		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());
		A = new int[N+1][N+1];
		S = new long[N+1][N+1];
		
		for(int row =1; row < N+1; row++) {
			st = new StringTokenizer(br.readLine());
			for(int column = 1; column < N+1 ; column++) {
				A[row][column] = Integer.parseInt(st.nextToken());
			}
		}
		
		for(int row =1; row < N+1; row++) {
			for(int column=1; column < N+1; column++) {
				S[row][column] = S[row-1][column] + S[row][column-1] - S[row-1][column-1] + A[row][column];
			}
		}
		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(S[x2][y2] - S[x1-1][y2] - S[x2][y1-1] + S[x1-1][y1-1]);
		}
	}

}