[BAEKJOON] 11660 구간 합 구하기 5

문제 요약

• 알고리즘 분류: 구간합, 누적합, 수학
• 난이도: Silver1
• 문제내용:
  • 2차원 배열을 주고 (x1, y1) ~ (x2, y2)의 합을 구해
• 사이트 : https://www.acmicpc.net/problem/11660

11660번: 구간 합 구하기 5

문제풀이

 

 이번문제는 2차원 배열의 누적합의 기본 문제이다. 누적합, 구간합에 대한 설명은 밑에 사이트에 참조하면된다. 밑에 사이트에 2차원 배열 누적합, 구간합을 이해하고 예제 코드에서 몇개만 추가만 하면되기때문에 따로 설명을 안한다.

 https://jih3508.tistory.com/50

[알고리즘 이론] 구간합, 누적합(prefix sum)

Code

Python

import sys
input = sys.stdin.readline
N, M = map(int, input().split())
matrix = [[0] * (N + 1)]
for _ in range(N):
    matrix.append([0] + list(map(int, input().split())))

prefix_sum = [[0] * (N + 1) for _ in range(N + 1) ]
for i in range(1, N + 1):
    for j in range(1, N + 1):
        prefix_sum[i][j] = prefix_sum[i-1][j] + prefix_sum[i][j-1] + matrix[i][j] - prefix_sum[i - 1][j - 1]
 
for _ in range(M):
    x1, y1, x2, y2 = map(int, input().split())
    print(prefix_sum[x2][y2]  + prefix_sum[x1 -1][y1 -1] - prefix_sum[x2][y1 - 1] - prefix_sum[x1 - 1][y2])

Java

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

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());
		int N = Integer.parseInt(st.nextToken());
		int M = Integer.parseInt(st.nextToken());
		
		int[][] matrix = 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++) {
				matrix[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		int[][] prefix_sum = new int[N + 1][N + 1];
		
		for(int i = 1; i <= N; i++) {
			for(int j = 1; j <= N; j++) {
				prefix_sum[i][j] =  prefix_sum[i-1][j] + prefix_sum[i][j-1] + matrix[i][j] - prefix_sum[i - 1][j - 1];
			}
		}
		
		int x1, y1, x2, y2;
		while(M-- > 0) {
			st = new StringTokenizer(br.readLine());
			x1 = Integer.parseInt(st.nextToken());
			y1 = Integer.parseInt(st.nextToken());
			x2 = Integer.parseInt(st.nextToken());
			y2 = Integer.parseInt(st.nextToken());
			System.out.println(prefix_sum[x2][y2]  + prefix_sum[x1 -1][y1 -1] - prefix_sum[x2][y1 - 1] - prefix_sum[x1 - 1][y2]);
		}
		
	}
			
}