백준 11660: 구간 합 구하기 5(java/python)

문제

---

풀이

이중 for문을 순회하며 (0, 0)부터 (i, j)인 지점까지의 합을 배열 arr에 저장하고, 이들을 적절히 가감하여 (x1, y1)부터 (x2, y2)인 지점까지의 누적 합을 계산한다.

 

전체 코드

 

1. 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));
		StringBuilder sb=new StringBuilder();
		
		StringTokenizer st=new StringTokenizer(br.readLine());
		int N=Integer.parseInt(st.nextToken());
		int M=Integer.parseInt(st.nextToken());
		
		int[][] arr=new int[N+1][N+1];
		
		for(int i=1; i<N+1; i++) {
			st=new StringTokenizer(br.readLine());
			
			for(int j=1; j<N+1; j++) {
				int n=Integer.parseInt(st.nextToken());
				arr[i][j]=arr[i][j-1]+arr[i-1][j]-arr[i-1][j-1]+n;
			}
		}
		
		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());
			
			int res=arr[x2][y2]-arr[x1-1][y2]-arr[x2][y1-1]+arr[x1-1][y1-1];
			sb.append(res).append("\n");
		}
		
		System.out.println(sb);
	}
}

 

 

2. python

import sys
input = sys.stdin.readline

N, M = map(int, input().split())

table = [[0]*(N+1) for _ in range(N+1)]
rows = [0]*(N+1)

for i in range(1, N+1):
    rows = [0] + list(map(int, input().split()))

    for j in range(1, N+1):
        table[i][j] = table[i][j-1] + table[i-1][j] - table[i-1][j-1] + rows[j]

for i in range(M):
    x1, y1, x2, y2 = map(int, input().split())

    res = table[x2][y2] - table[x1 - 1][y2] - table[x2][y1 - 1] + table[x1 - 1][y1 - 1]

    print(res)