[백준 11660] 구간 합 구하기 5 Java 풀이

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

 

접근

n의 크기가 1,024이고, 합을 구해야 하는 횟수가 100,000입니다. 구간마다 합을 매번 계산하면 1초안에 모든 구간의 합을 계산할 수 없습니다. 구간 합을 이용하면 시간 복잡도를 O(n)에서 O(1)로 줄여 문제를 해결할 수 있습니다. 그러므로 모든 구간의 합을 구하는 데에는 총 시간 복잡도가 O(M)이 될 것입니다.

 

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		// 입력 처리
		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		// 누적 합 초기화
		int[][] s = new int[n + 1][n + 1];
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= n; j++) {
				s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + Integer.parseInt(st.nextToken());
			}
		}

		// (x1, y1)부터 (x2, y2)까지 합을 구한다.
		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());
			sb.append(s[x2][y2] - s[x1 - 1][y2] - s[x2][y1 - 1] + s[x1 - 1][y1 - 1]).append("\n");
		}

		// 결과 출력
		System.out.println(sb);
	}
}