[백준 11660] 구간 합 구하기 5 Java 풀이

11660번: 구간 합 구하기 5

 

풀이

구간마다 합을 계산하면 1초 안에 계산을 끝낼 수 없기 때문에 구간 합을 이용해서 문제를 해결합니다.

 

2차원 배열 구간 합 공식

prefixSum[r][c] = prefixSum[r][c - 1] + prefixSum[r - 1][c] - prefixSum[r - 1][c - 1] + arr[r][c]

 

질의 (x1, y1), (x2, y2)에 대한 구간 합 공식

prefixSum[x2][y2] - prefixSum[x1 - 1][y2] - prefixSum[x2][y1 - 1] + prefixSum[x1 - 1][y1 - 1]

 

코드

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

public class Main {
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringBuilder sb = new StringBuilder();

		StringTokenizer st = new StringTokenizer(br.readLine());
		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		int[][] sum = 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++) {
				// 2차원 누적 합
				sum[i][j] = sum[i][j - 1] + sum[i - 1][j] - sum[i - 1][j - 1] + Integer.parseInt(st.nextToken());
			}
		}

		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());
			sb.append(sum[x2][y2] - sum[x2][y1 - 1] - sum[x1 - 1][y2] + sum[x1 - 1][y1 - 1]).append("\n");
		}
		System.out.println(sb);
	}
}

add 11660 · jinseoplee/baekjoon-solutions@87c73ac