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

😊 문제

백준 11660 - 구간 합 구하기 5

😊 풀이

해당 문제는 2차원 구간 합 배열 문제입니다.
N×N개의 수가 N×N 크기의 표에 채워져있고 (x1, y1)부터 (x2, y2)까지 합을 구합니다.

예를 들어, N=4이고 (2,2)부터 (3,4)까지 합을 구하면 3+4+5+4+5+6 = 27입니다.
표에서 0행 과 0열은 모두 0으로 가정하고 문제풀이 해주었습니다.

D[2][2]를 구하고 싶다면

D[1][2]+D[2][1]-D[1][1]+A[2][2] 방식으로 풀이해주면 됩니다.

D[i][j] 구간합 배열값을 초기화 하기 위한 공식
D[i][j] = D[i-1][j]+D[i][j-1]+D[i-1][j-1]+A[i][j]

(x1, y1)부터 (x2, y2)에 대한 구간합 구하기

만약 (2,2) 에서 (3,4) 의 구간합을 구하고 싶다면
1. (1,4)의 구간합과 (3,1)의 구간합을 빼준 후
2. 중복해서 빼준 (1,1)의 구간합을 더해줍니다.

(x1, y1)부터 (x2, y2)에 대한 구간합 구하는 공식
D[x2][y2] = D[x1-1][y2]-D[x2][y1-1]-D[x1-1][y1-1]

😊 코드

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

//2차원 구간 합 배열
public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(bf.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 + 1; i++) {
			st = new StringTokenizer(bf.readLine(), " ");
			for (int j = 1; j < N + 1; j++) {
				A[i][j] = Integer.parseInt(st.nextToken());
			}
		}

		int D[][] = new int[N + 1][N + 1]; // 구간합 배열 생성

		for (int i = 1; i < N + 1; i++) {
			for (int j = 1; j < N + 1; j++) {
				D[i][j] = D[i][j - 1] + D[i - 1][j] - D[i - 1][j - 1] + A[i][j];
			}
		}

		// 총 M줄에 걸쳐 (x1, y1)부터 (x2, y2)까지 합을 구해 출력한다.
		for (int i = 0; i < M; i++) {
			st = new StringTokenizer(bf.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());

			int result = D[x2][y2] - D[x1 - 1][y2] - D[x2][y1 - 1] + D[x1 - 1][y1 - 1];
			System.out.println(result);
		}

	}

}