11660. 구간 합 구하기 5 (자바, 코딩테스트, 백준)

문제

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

11660번: 구간 합 구하기 5

---

풀이

검정색 부분은 0으로 채웠다고 생각하자 (편의상)

이전 문제의 구간 합 구하기 4번의 업그레이드 버전 1차원 부분합 풀이가 아닌 2차원 부분합을 고려하면 된다.

녹색 범위안의 합계를 구하기 위해서 생각해본다면 (연두색 부분은 만들어질 때 누적합으로 만들어진다고 생각) 

(기존에 들어갈 값) - (자신을 기준으로 위쪽값) - (자신을 기준으로 왼쪽값) 이렇게 만 한다면 

자신기준 좌측 상단부분에 있는 값은 두번 반복되어 붉은색에 빠지기 때문에 좌측 상단 값은 한번 더해야 한다.

 

아래 코드에서 

table[i][j] = Integer.parseInt(st.nextToken());
table[i][j] += (table[i - 1][j] + table[i][j - 1] - table[i - 1][j - 1]);

부분을 확인해보면 쉽게 이해가 될 것이다.

---

나의 코드

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

public class Solution_BJ_11660 {
	public static void main(String[] args) throws Exception {
		BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();
		String[] l_r = bf.readLine().split(" ");
		int N = Integer.parseInt(l_r[0]), M = Integer.parseInt(l_r[1]);
		int[][] table = new int[N + 1][N + 1];

		StringTokenizer st;
		for (int i = 0; i < table.length; i++) {
			table[i][0] = 0;
			table[0][i] = 0;
		}

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

		for (int m = 0; m < M; m++) {
			st = new StringTokenizer(bf.readLine());
			int target = 0;
			int x1 = Integer.parseInt(st.nextToken());
			int y1 = Integer.parseInt(st.nextToken());
			int x2 = Integer.parseInt(st.nextToken());
			int y2 = Integer.parseInt(st.nextToken());

			target = table[x2][y2] + table[x1 - 1][y1 - 1] - table[x2][y1 - 1] - table[x1 - 1][y2];
			sb.append(target + "\n");
		}
		System.out.println(sb);
	}
}