🐣 백준 Q11660 - 구간 합 구하기 5 (java)

문제

---

• 백준 Q11660 - 구간 합 구하기 5

풀이 순서

---

1. A[][] : 값들을 입력받아 2차원 배열에 넣어준다.
   1. D[][] : (1,1) ~ (i, j)까지의 구간의 합을 배열에 다시 넣는다.
2. (x1, y1), (x2, y2) : 필요한 값들을 입력받고
3. 구간의 합을 구해놓은 D[][]배열을 사용해 필요한 값을 구한다.

코드

---

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

public class Q11660_구간합구하기5 {
	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 A[][] = 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++) {
                A[i][j] = Integer.parseInt(st.nextToken());
            }
		}

		int D[][] = new int[N+1][N+1];
        for (int i = 1; i <= N; i++) {
			for (int j = 1; j <= N; j++) {
				// 구간의 합 구하기
				D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[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());
			// 구간 합 배열로 질의에 답변하기
			// (x2, y2)  - (필요없는 부분의 세로) - (필요없는 부분의 가로) + (가로, 세로로 겹치는 부분)
			int result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1];
			System.out.println(result);
		}
	}
}

/*
----- 예제 입력 1 -----
4 3
1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7
2 2 3 4
3 4 3 4
1 1 4 4
----- 예제 출력 1 -----
27
6
64

 */

그림으로 이해

---

구간의 합을 구해 배열에 채워넣는 부분의 코드는

int D[][] = new int[N+1][N+1];
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
		// 구간의 합 구하기
			 D[i][j] = D[i][j-1] + D[i-1][j] - D[i-1][j-1] + A[i][j];
			}
		}

구간의 합으로 채워져 있는 배열을 이용해 필요한 값을 구하는 코드는

// 구간 합 배열로 질의에 답변하기
// (x2, y2)  - (필요없는 부분의 세로) - (필요없는 부분의 가로) + (가로, 세로로 겹치는 부분)
int result = D[x2][y2] - D[x1-1][y2] - D[x2][y1-1] + D[x1-1][y1-1];