백준 11660 구간 합 구하기 5

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

 

 이 문제는 정수가 쓰여진 표가 주어지고 x1,y1부터 x2,y2까지의 구간합을 구하는 문제이다. 이 문제에서 구해야 하는 횟수가 최대 십만번 이므로 필자는 미리 각 점에서의 구간합들을 구하고, 표에서 구해야 하는 구간합만 구하는 식을 이용하여 답을 찾아냈다. 이 식은 다음 표를 이용하여 구했다.

 먼저 우리는 0,0부터 x,y까지의 구간합을 구한 테이블을 구해야 한다. 이는 간단히 구할 수 있으니 패스하겠다.

 위 그림을 보면 x2,y2와 x1,y1 사이의 구간합은 노란색이다. 이 노란색을 구하는 법은 (x2,y2) - (x1-1,y2)-(x2,y1-1) + (x1,y1)이다. 이러한 것들을 그냥 코드로 구현하면,

import sys
input = sys.stdin.readline

L,t = map(int,input().rstrip().split())

table = []
matrix = [[0 for a in range(L+1)] for b in range(L+1)]
for _ in range(L):
    table.append(list(map(int,input().rstrip().split())))

for a in range(1,L+1):
    for b in range(1,L+1):
        if a==1 and b==1:
            matrix[a][b] = table[a-1][b-1]
        elif a==1:
            matrix[a][b] = matrix[a][b-1] + table[a-1][b-1]
        elif b==1:
            matrix[a][b] = matrix[a-1][b] + table[a-1][b-1]
        else:
            matrix[a][b] = matrix[a][b-1]+matrix[a-1][b] - matrix[a-1][b-1] + table[a-1][b-1]

for i in range(t):
    x1,y1,x2,y2 = map(int,input().rstrip().split())
    print(matrix[x2][y2]-matrix[x1-1][y2]-matrix[x2][y1-1]+matrix[x1-1][y1-1])