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

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

11660번: 구간 합 구하기 5

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

 

누적 합 구하기

배열을 전부 받은 후, map[i][j]에는 (0, 0)부터 (i, j)까지의 모든 합이 들어가도록 계산했다. 우선 각 행의 0부터 N까지 열을 누적하고, 모든 행을 완료한 후에는 열을 기준으로 각 행을 누적해주었다. 예를 들어 예제 1이라면 누적된 배열은 다음과 같다. (계산하기 쉽도록 0행과 0열은 0으로 채워주었다)

// 예제 1 배열
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

// 누적된 배열
[0, 0, 0, 0, 0]
[0, 1, 3, 6, 10]
[0, 3, 8, 15, 24]
[0, 6, 15, 27, 42]
[0, 10, 24, 42, 64]

 

주어진 범위의 합 구하기

노란색 칸의 합을 구한다고 해보자. 즉, (3, 3)부터 (4, 4)까지의 합을 구하는 것이다. 이미 구해놓은 누적 배열에서 (4, 4)를 보면 64이다. 이는 (1, 1)부터 (4, 4)까지를 모두 더한 값이다.

 

빨간색 칸을 보자. 빨간 색 칸은 (1, 1)부터 (2, 4)까지를 더한 값이다. 즉 빨간색 범위를 모두 더한 값이다.

파란색 칸도 동일하게 (1, 1)부터 (4, 2)까지, 파란색 범위를 모두 더한 값이다.

 

따라서 전체 칸에서 빨간색 범위와 파란색 범위의 합을 빼고, 중복된 회색 칸의 합(누적 배열의 (2, 2))을 더해주면 노란색 칸의 합을 알 수 있다. 예제 1의 첫번째 범위 (2, 2) ~ (3, 4)를 구한다면 다음과 같다.

 

// 누적 배열에서
// (3, 4)의 값 - (1, 4)의 값 - (3, 1)의 값 + (1, 1)의 값

42 - 10 - 6 + 1 = 27

 

전체 코드

// 시간 : 744ms
// 메모리 : 127232KB
public class Main {

	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());
		
		int[][] map = 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++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		for (int i = 0; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				map[i][j] += map[i][j - 1];
			}
		}
		
		for (int j = 0; j <= N; j++) {
			for (int i = 1; i <= N; i++) {
				map[i][j] += map[i - 1][j];
			}
		}
		
		StringBuilder sb = new StringBuilder();
		for (int t = 0; t < M; t++) {
			st = new StringTokenizer(br.readLine());
			int r1 = Integer.parseInt(st.nextToken());
			int c1 = Integer.parseInt(st.nextToken());
			int r2 = Integer.parseInt(st.nextToken());
			int c2 = Integer.parseInt(st.nextToken());
			
			int n = map[r2][c2] - map[r1 - 1][c2] - map[r2][c1 - 1] + map[r1 - 1][c1 - 1];
			sb.append(n).append("\n");
		}
		
		System.out.print(sb);
	}

}