145. 11660(구간 합 구하기 5) - 자바

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

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

		int N = Integer.parseInt(tmp1[0]);
		int M = Integer.parseInt(tmp1[1]);

		int[][] arr = new int[N + 1][N + 1];

		// 값 넣기
		for (int i = 1; i < N + 1; i++) {
			String[] tmp2 = br.readLine().split(" ");
			for (int j = 1; j < N + 1; j++) {
				arr[i][j] = Integer.parseInt(tmp2[j - 1]);
			}
		}

		// 누적합 구하기
		for (int i = 1; i < N + 1; i++) {
			for (int j = 1; j < N + 1; j++) {
				arr[i][j] = arr[i][j] + arr[i][j - 1] + arr[i - 1][j] - arr[i - 1][j - 1];
			}
		}

		// 본게임 시작
		for (int i = 0; i < M; i++) {
			String[] tmp3 = br.readLine().split(" ");
			int x1 = Integer.parseInt(tmp3[0]);
			int y1 = Integer.parseInt(tmp3[1]);
			int x2 = Integer.parseInt(tmp3[2]);
			int y2 = Integer.parseInt(tmp3[3]);

			int tmp = 0;
			tmp = arr[x2][y2] - arr[x2][y1 - 1] - arr[x1 - 1][y2] + arr[x1 - 1][y1 - 1];

			sb.append(tmp).append("\n");
		}
		System.out.print(sb);

	}
}

문제요약

2차원 배열의 누적합을 구하라.

설명

 

1단계 누적합 구하기

예를 들어 (3,3) 의 합을 구하고 싶다고 하자.

먼저 (0,0) ~ (2,3) 의 합을 구한다 (1 + 2 + 3 + 2 + 3 + 4 = 15)

다음에는 (0,0) ~ (3,2) 의 합을 구한다 (1 + 2 + 2 + 3 + 3 + 4 = 15)

(0,0) ~ (2,2) 는 두번 더해주었기 때문에 한번 빼준다. (1 + 2 + 2 + 3 = 8)

 

따라서 (3,3)의 합은 5 + 15 + 15 - 8 = 27이된다.

 

이것을 누적합을 이용하여 적용해보면,

(3,3)의 누적합 = (3,3)의 값[5] + (2,3)의 누적합[15] + (3,2)의 누적합[15] - (2,2)의 누적합[8] 이라는 식을 만들 수 있다.

 

2단계 구간별 누적합 구하기

아래와 같이 (2, 2)부터 (3, 4)까지 합을 구하고 싶다고 하자.

 

그러면 (3,4)의 합에서

(3,4)의 합은 42

행이 1이고 열이 4까지의 합을 빼주고 (1 + 2 + 3 + 4 = 10)

행이 3이고 열이 1까지의 합을 빼준다. (1 + 2 + 3 = 6)

마지막으로 (1,1)의 합은 두번 빼주었으므로 한번 더해준다.

 

그러면 42 - 10 - 6 + 1 = 27 이 된다.

 

이를 누적합으로 구하면 

다음과 같이

(2,2) ~ (3,4)의 구간합 = (3,4)의 누적합[42] - (1,3)의 누적합[10] - (3,1)의 누적합[6] - (1,1)의 누적합[1]이라는 식을 만들 수 있다.

 

		String[] tmp1 = br.readLine().split(" ");

		int N = Integer.parseInt(tmp1[0]);
		int M = Integer.parseInt(tmp1[1]);

		int[][] arr = new int[N + 1][N + 1];

		// 값 넣기
		for (int i = 1; i < N + 1; i++) {
			String[] tmp2 = br.readLine().split(" ");
			for (int j = 1; j < N + 1; j++) {
				arr[i][j] = Integer.parseInt(tmp2[j - 1]);
			}
		}

배열은 기본적으로 0부터 시작하니 [2][2] 가 진짜 [2][2]가 될 수 있도록 행이 0인 부분에는 전부 0을, 열이 0인 부분에도 전부 0을 저장한다.

		// 누적합 구하기
		for (int i = 1; i < N + 1; i++) {
			for (int j = 1; j < N + 1; j++) {
				arr[i][j] = arr[i][j] + arr[i][j - 1] + arr[i - 1][j] - arr[i - 1][j - 1];
			}
		}

각 부분에 부분합을 구해준다.

		// 본게임 시작
		for (int i = 0; i < M; i++) {
			String[] tmp3 = br.readLine().split(" ");
			int x1 = Integer.parseInt(tmp3[0]);
			int y1 = Integer.parseInt(tmp3[1]);
			int x2 = Integer.parseInt(tmp3[2]);
			int y2 = Integer.parseInt(tmp3[3]);

			int tmp = 0;
			tmp = arr[x2][y2] - arr[x2][y1 - 1] - arr[x1 - 1][y2] + arr[x1 - 1][y1 - 1];

			sb.append(tmp).append("\n");
		}
		System.out.print(sb);

총 M번 진행될 것이다.

위에서 구한 누적합을 이용하여 2단계 식처럼 계산하여 tmp에 저장하고 sb에 저장하여 한번에 출력해 줄 것이다.