[Baekjoon] 2167_2차원 배열의 합

Silver V

문제(출처: https://www.acmicpc.net/problem/2167)

---

< 2차원 배열의 합 >

 

문제 풀이 

 

(i, j) 위치부터 (x, y) 위치까지에 저장되어 있는 수들의 합을 구하기 위해서는 미리 누적합을 구해둔다.

누적합을 구하는 방법은 다음과 같다.

 

2번의 누적합은 [2 = 1+2번의 값], 3번의 누적합은 [3 = 1+3번의 값]이다.

(0,0)부터 (1,1)까지 누적합을 구하는 방법은 [4 = 3+2-1+4번의 값]이다.

누적합을 구한 배열에서 빨간 박스 영역의 넓이를 구하는 방법은 [넓이 = 12-10-4+2]이다.

 

 my solution (Java)

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

public class _2167_ { // 2차원 배열의 합

	public static void main(String[] args) throws IOException {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
		StringTokenizer st = new StringTokenizer(bf.readLine());

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int arr[][] = new int[n + 1][m + 1];
		for (int i = 1; i <= n; i++) {
			st = new StringTokenizer(bf.readLine());
			for (int j = 1; j <= m; j++) {
				int num = Integer.parseInt(st.nextToken());
				arr[i][j] = arr[i - 1][j] + arr[i][j - 1] - arr[i - 1][j - 1] + num;
			}
		}

		int k = Integer.parseInt(bf.readLine());
		for (int l = 0; l < k; l++) {
			st = new StringTokenizer(bf.readLine());

			int i = Integer.parseInt(st.nextToken());
			int j = Integer.parseInt(st.nextToken());
			int x = Integer.parseInt(st.nextToken());
			int y = Integer.parseInt(st.nextToken());

			int sum = arr[x][y] - arr[i - 1][y] - arr[x][j - 1] + arr[i - 1][j - 1];
			bw.write(sum + "\n");
		}
		bw.flush();
	}
}

변수)
n, m : 배열의 크기
arr : 배열의 누적합
k : 합을 구할 부분의 개수
i, j, x, y : 합을 구할 영역

 

배열의 크기를 입력받는다. 배열의 크기만큼 배열의 값을 입력받으면서 누적합을 바로 구한다. 합을 구할 부분의 개수 k를 입력받는다. 합을 구할 영역 i, j, x, y를 입력받아 영역의 합을 구한 후 출력한다.

---

---