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

문제

 

 

접근 방식

1차원 배열의 구간합 원리를 2차원 배열에 적용하면 풀 수 있는 문제다.

1 2 3 4
2 3 4 5
3 4 5 6
4 5 6 7

 

위와 같은 배열이 주어졌을 때 2,2 부터 3,4까지의 구간합을 구하려면

2,2 ~ 2,4의 구간합 + 3,2 ~ 3,4의 구간합을 더해주면 된다.

1 3 6 10
2 5 9 14
3 7 12 18
4 9 15 22

 

위처럼 각 행마다의 누적합을 구해둔 후에

이 누적합을 이용해 각 행의 특정 부분의 구간합을 구해주면 된다.

 

예를 들어 2,2 ~ 2,4까지의 구간합은

2,4까지의 누적합에서 2,1의 누적합을 뺀 것이고

3,2 ~ 3,4까지의 구간합은

3,4까지의 누적합에서 3,1의 누적합을 뺀 것이다.

 

결국 x축을 기준으로 시작 x축부터 끝나는 x축까지 반복하며

각 행의 구간합을 구하여 더해주면 된다.

 

풀이

public class Main {

	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = new StringTokenizer(br.readLine());
		StringBuilder sb = new StringBuilder();

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

		long[][] dp = new long[n + 1][n + 1];

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

		while (m-- > 0) {
			st = new StringTokenizer(br.readLine());

			int sx = Integer.parseInt(st.nextToken());
			int sy = Integer.parseInt(st.nextToken());
			int ex = Integer.parseInt(st.nextToken());
			int ey = Integer.parseInt(st.nextToken());

			long result = 0;

			for (int i = sx; i <= ex; i++) {
				result += (dp[i][ey] - dp[i][sy - 1]);
			}

			sb.append(result).append("\n");
		}

		System.out.println(sb);
	}
}